Powering a stepper motor (on Arduino), what's too much and too little?
I would use C or D batteries for initial testing. You may need the increased current capacity to power your motor successfully.
Remember that the GND of the Arduino needs to be connected to the GND of the motor battery pack of four (6 V nominal) C or D cell battery pack.