The torque output of an electric motor is directly proportional to the motor current, and the current (I) is roughly equal to
Where V is the motor supply voltage, R is the winding resistance and ε is the back-electromotive force (back EMF).
The back EMF is the voltage that would be present at the motor terminals without anything being connected. It is produced by the motor acting as a generator, if you will, and it's proportional to the rotation speed.
If you connect an unloaded motor to a power supply, it will speed up until the back EMF exactly cancels out the supply voltage and then spin at a constant speed. If torque is demanded from the motor (even just the slight friction of spinning), it reaches a speed where the winding resistance lets just enough current to flow to balance any torque.
When you first switch your motor on, the speed is zero. This means that the back EMF is also zero, so the only things limiting the motor current are the winding resistance and the supply voltage. A motor which is rated for 500 mA and draws 50 mA without any load at 6 V might very briefly draw several amps of current when first switched on.
Apparently your setup somehow manages to supply this inrush current of one motor, but two motors starting at the same time draw so much current that the supply voltage drops below the level required by the arduino to function, causing it to reset and release the relay.
You need to limit the current draw of your motor when it first starts up so that the voltage stays stable. There are several ways to do this:
The simplest method is to add a current limiting resistor in series with the two parallel motors. For example, a 10 ohm resistor would limit the current to a maximum of 600 mA, assuming a 6 V supply. The resistor has to be a 3.6 W (or better rated) power resistor. The drawback is that you are wasting power in the resistor, and your maximum torque at speed will be severely limited.
You can use a current limiting resistor in combination with an extra relay, so that you can remove the resistor from the circuit after the motors have reached their full speed.
The optimum way is to use a semiconductor motor driver. They are more complicated to control, but they allow control over the average motor voltage (via pulse width modulation) and thus of the motor speed. By slowly ramping up the voltage from zero, you can keep the difference between the motor voltage and back EMF ("speed induced voltage") low, and consequently keep the current low.