Minimise power draw from Steppers OR New battery+motor choice for Robot

I've been building an Arduino-compatible two-wheeled robot based on the @ShrimpingIt circuit and 28-BYJ-48 motors with a JY-MCU Bluetooth Serial Module. Progress had stalled as I was experiencing Bluetooth brownouts over and over again. Having followed a million dead ends on what was going on with Bluetooth and serial, this now seems to be because the battery packs are going flat super-quick, but so fast that I couldn't really believe that was the real issue.

The robot is only designed to carry the weight of its own breadboard, but it can take a 4xAAA battery pack (with cheap alkalines) from 6.5V to 5V within just over a minute of unloaded rotation (even with the axles running free).

Now I desperately need to come up with something which will keep the robots going on a battery pack for at least 10 minutes or more else they won't be any use in the classroom they're destined for. Various alternatives to address the crazy power draw;

To drive the robot, I currently have two 28-BYJ-48 stepper motors which are being driven by the Accelstepper library. Are these motors even realistic to use on battery? I'm wondering what possible circuit changes or software controls might change their power demands, or whether they are inherently unbelievably inefficient and I should give up. If so, what motor options have people had success with, (I'm hoping to be able to count rotations for control purposes, though, hence the steppers, so something which can do this would be great).

On the battery front, what sort of plan makes sense. For example can I hope to use cheap Alkaline batteries, or is this a fool's game? Do I have to go all the way to something high-end like LiPo? Anything in the middle which could be cheap? I'm aiming at sub-£10 all-in which I'd pretty-much achieved with the prototype, so it would be a shame to have super-expensive batteries in the design.

Overall, what kind of motor and battery configuration should I expect to be able to get a 10 minute-plus run time from breadboarded-ATMEGA-based two-wheeled robots, even if the robots are fairly slow-moving (i.e. not bombing around like remote-controlled cars)?

FOR REFERENCE

You can see the Accelstepper config in...

...which can be diffed against the StandardFirmata distributed with Arduino.

I'm basing the core serial protocol on Firmata, and then just extending it to be able to send Stepper positions and get back Ultrasonic pings. The 'client-side' control of the robot takes place using a python script, building on pyFirmata, allowing me to access any sensors on the robot, and also control its Robot-specific capabilities on top...