15 years ago I did a geeky study of the performance of flashlight batteries, and also that of the various types of bulbs. I kept track of run time of each flashlight/battery combination, at temperatures of 70* F (in the house) and also at temperatures of ~+32* F and 0* F on the patio. The batteries I tested were Duracell alkaline, Energizer Ni-MH rechargeables, and Energizer lithiums. I found that the Duracell alkalines petered out at about +32* F, the rechargeables at about +30* F, and the lithiums not at all even at temperatures down to 0* F.
The rechargeables worked best if I had charged them up the day of the test. They did have a significant loss of charge over 1-2 weeks (self-discharge). I assume that the technology of rechargeables has improved over the past 15 years, but I still rather doubt that they will perform well at much below freezing temperatures. My summer stint at McMurdo in Antarctica convinced me that the only battery worth using in severe cold was a lithium one.