I use a Cateye Strada Slim. Never used it in that type of cold. It uses replacable button Lithium 1032 in the sensor (the head is a different one). It does have large digits that might be handy when your eyes are half frozen shut.

I have found the 1032 LIthiums work at 0 degrees in other devices. The advantage with replacable is a warm battery can be kept on your person. I have been in sub-zero with my Canon F-1n with a Lithium and no issues (even if it did that camera could work without a battery, but no metering.) Rechargables are not as effective in real cold and can be damaged if run down, as RMueller said in Post #5 . In winter I carry my phone in a flapped shirt pocket instead of the belt holster to keep it warm.