As is suggested, there is a temperature range for a given performance level. Until the electolyte actually freezes, it will still work, although peak output may be drastically reduced.
As long as there is some ion mobility at -40C, the battery will work. The problem is that all chemical reactions are temperature sensitive, so the peak output at -40C is likely to be about 1.5% of what it is at 20C. If you application only needs say 25ma, then it probably works at -40C. If it needs 100ma, it probably works OK at -20C, but not much below -20C.
If you need 500ma, forget it at those sorts of temperatures. There are quite a few applications that only draw 100ma or so, if you only need 25ma, there are less expensive solutions.
The temperature at which the electrolyte crystalizes (freezes) is the point at which it will stop working all together.
Increasing temperature increases reaction rates,and increase the maximum available current, it also increases the self discharge rate.
Anyone who doubts the effect of temperature on batteries should simply look outside in Chicago on the first day of winter where the temperature went below zero. How many cars refused to start? Lower temperature restricts ion mobility in the electrolyte, and dramatically reduces maximum current delivered.