The first thing I'd try is a capacitor across the battery. Maybe 1000uF for starters. If a 1000uF capacitor works but it 's physically too big, you can experiment with smaller capacitors.
Or, a capacitor across the Arduino's power supply connectors, plus a diode in-between the battery and Arduino (with the motors connected directly to the battery). The diode prevents the capacitor from discharging into the motors*, but a regular silicon diode will have about a 0.6V drop across it. If the voltage drop is problem, a Schottky diode will have about 0.2V across it.
(You can't generally use an RC filter in a power supply because there is too much voltage drop across the resistor.)
- The diode makes the capacitor more effective in filtering-out negative voltage spikes when the motor suddenly draws more current. But with positive spikes, it's no more effective than the capacitor alone. However, the Arduino's on-board regulator should be very effective in killing positive spikes.