What are the consequences of allowing paint to freeze?
I have an idea for you. Instead of insulating and heating the entire garage to save a few gallons of paint, perhaps you could build a small insulated paint locker. Build a box or cabinet large enough to store all your paints. Insulate the inside with some 2 inch rigid foam or R-11 blanket insulation and put some foam weather stripping around the insulated door or cover to make it fairly air tight.  You could then install a low wattage light bulb as a source of heat. Honeywell makes an inexpensive plug=in/plug outlet feed thermostat that would work fantastic in this application.  I use one for running three 40 watt clamp-on light fixtures in the engine compartment of my boat.  The thermostat can be set to turn on the lights when the temp lowers to 35 to 40F and turn off at 40 to 50F. You set it to keep the locker above freezing. I wish I was good at drawing pics with the puter, but a good design would be to mount your lights and thermostat at the very bottom of the locker with a venting or wire shelf just above, so the heat rises in the locker and the bulbs are protected from getting bumped by paint cans. I'm sure you could build the whole project for under $100. The bonus is that something like this would be very cheap to run all winter.