In general, there are two problems with low temperatures:
- The battery capacity is severely reduced; the lower the temperature the less usable capacity.
- Lubricant or bearings used for the moving parts of the camera may stiffen, so it takes more power to move the shutter and mirror, possibly more than the battery can deliver.
Lubricants in cold weather:
Depending on the characteristics of the lubricant itself, it may even start to take on certain properties of a solid and essentially "freeze" (for lack of a better description) with catastrophic results. Most base oils and grease are able to withstand moderate temperature dips to zero degrees Celsius and many to -10 degrees Celsius without much decrease in performance. At the level of -20 degrees Celsius and beyond, however, certain lubricants become unsuitable.
If camera lubricants or bearings is the issue, you'd need to warm the whole camera. I wonder if that's the problem in your case - I've never had the issue with half-exposed frames for instance, I'm just seeing the battery charge indicator drop almost picture by picture, and the camera turning ifself off when the charge becomes low enough. (But I've never tried high fps in cold weather either.)
Sorry, but I don't know any good solutions for dealing with that. Apart from what you are already doing - bring the camera indoors and thaw it out.
The battery capacity can normally be dealt with by warming the battery. I've found swapping batteries fairly effective: Keep a spare battery in an inner pocket so it's kept warm by body heat (shirt breast pockets are good; outer pockets are almost as cold as the external temperature, and won't help much), and swap them when needed.
With swapping, I'd expect perhaps 50-60% capacity loss, so two batteries would last a bit shorter than what one battery does in room temperature.
Without swapping, I'm seeing something like a 90-95% capacity loss already at -5°C to -10°C (23°F to 14°F), so I can only get off a handful of shots before running out of battery.
Alternatively, use an external battery pack. Here's a DIY hack where somebody soldered on a high-capacity LiPo (Lithium Polymer) battery and made their Canon 60D operate for hours of time lapse in -16°C (3°F).
The disadvantage is that you need to be somewhat familiar with electricity and electronics to go the DIY route; getting the voltage or polarity wrong could easily kill the camera.
There are a few off-the-shelf external battery packs. I have no experience with any of these, but ideally I'd pick one with high capacity and a long cable, so I could keep the battery inside my jacket.