You can power an Arduino just fine with 12V, as long as you don't add much other loads to the Arduino (or indeed the regulator will overload). Just add a second connection to your power supply for the motors - best to connect the two right at the power supply to suppress noise making it to the Arduino.
Alternatively, use a buck converter to step down the 12V to 5V and use that to power the Arduino through it's Vcc pin (so bypassing the regulator). 1-2A buck converters are cheap and easy to find.