Well, try powering the whole setup with a 12v wall wart and measuring the current. Divide the capacity of the batteries (in amp-hours) by the current draw (in amps). That will give you the approximate runtime.
Having just read a later post where one battery pack was used to power the Arduino, plus shield and motor, it seems this may be a no no as the gentleman was having issues.
So is it better to power the Arduino with say a 9V battery, and the motor shield plus stepper with a separate 12V battery? I appreciate that all the negative leads be tied together
Yes, motors will give the Arduino power supply glitches. But try not to use a 9V battery. 6x AA batteries will last a LOT longer. Power the motors separately by all means.
You may find a DC-DC converter to generate a lower voltage from the 12V is a good approach,
since it will handle the vaguaries of the 12V motor supply and be efficient. When you say stepper
shield, can you clarity which board you mean and which motor you have / are thinking of?
A 9-volt battery gives you the worst capacity-to-price ratio. I use one for a few weeks, occasionally using it to power my 3A 5V regulator. Understandably, it dies pretty fast.