Which battery should I use to power arduino+motor shield + two 200 RPM (3.6V/1.5A)motors
I have run into similar weirdness myself, and the solution that worked for me is to have separate batteries for the Arduino and the motors. This is more important if your motors run at a different voltage (e.g. 6v or 12v motors), but is useful in any case. This means that, when the motors draw to much from the batteries, the motors will slow down. If the same battery is used for the motors as for the Arduino, then the voltage drop from the motors will also apply to the Arduino; if the voltage drops in the Arduino, it will turn off (and turn back on when the voltage is restored). This is likely what you are seeing.