Just get a motorcycle battery or even a car battery. I have a motorcycle battery that dishes out 12v at 18Ah. You can use the 9.6v battery packs to power the circuitry, and use the 12 volt battery to only power the motor(s). Thats what I would suggest. Thats basically like the setup for the $50 robot with the 9v battery and the 4 AA battery back except with 12v and 9.6v instead of 9v and 6v. Though I would try to get a smaller battery for the circuitry only battery. Such as the 6v battery pack suggested for the $50.
Also, what you can do is get four 6v batteries, put two pairs in series with eachother and then hook those two series pairs in parallel so you get a 12v supply with double the Ah-age that you would get with just two 6v batteries in series. Then, to run your circuitry, you can simply draw power from one 6v battery.
Hope this helps
~Dragon