This is an educated guess, but I think it becomes less efficient, so it heats up, and then performs better as it heats. I assume this to be the case because I charge my RC plane LiPos the same way every time, and they take the same amount of energy, but flying in the winter gives much shorter flight times. Since the battery is warm after a flight, even in the cold, I don't think the energy is still there the battery is still discharged when I take it home), so it must just be much less efficient and wasting a lot of energy as heat.

I assume it's just that its internal resistance rises when it's cold, but I might be wrong.