H Bridge not working with two DC motors on paralell -- Arduino
There are many issues here.  A 6v-nominal battery is insufficient for the Vin of a typical Arduino, as the regulator has a high drop-out voltage.  And as it discharges or is loaded, the battery voltage will only get lower.  

Additionally, the dropout voltage of most regulators increases the more current they have to supply.  And you should really not be running relay coils off of the Arduino's regulator to begin with.

Of course adding a second motor in parallel only increases the battery sag.

What current do your motors typically require?  If not too high, you might consider a modern FET bridge like a TB6612FNG - that will be quieter, give you unique control of each motor, and let you use PWM to modulate the drive, too.