If you can arrange your bulbs in strings of three, they should be happy with a nominal 12 volts, and the current should be more manageable.
There are devices out there that have a 12 volt input and a lower voltage output without generating a lot of heat, but the devil is in the price (probably). If you measure how much current one of the bulbs takes for an acceptable light output, again, we should be able to come up with some sound suggestions. If all the bulbs are in parallel, the total current will be twenty times that of one, whether off 4.5 volts or 12 volts and regulated. Best guess at the moment is three or four high capacity Nicads or NiMH cells for the lights, purely to keep it simple. Lights have a distressing habit of taking more power than the main motor.