Which battery should I use to power arduino+motor shield + two motors
This is a hard question to answer without knowing a few more things about your components.


If you run the motors at 3.6V, or close to that, how much current do they require? You could measure this using a multimeter in series with your motor and an about 3.6V power supply.


Since they run at a pretty low voltage, I'd guess the motors require quite a bit of current, or they're relatively low power machines. That's probably why the 9V batteries don't work. Regular 9V alkaline batteries can't provide much current.


Is the red light blinking on your shield an overcurrent indication? Trying to run a 3.6 v motor at 18v is probably going to be bad for the motor in the long run (or not so long), and it could certainly result in a lot of current going through the motor driver and causing it to shut off.


One thing you could try is using your 18v battery, but running the motor at a very low duty cycle setting. Are you using the shield based on the MC33932? If so, it supports duty cycle control. Theoretically, you shouldn't exceed 20% duty cycle with an 18v battery (3.6/18=0.2 or 20%).