To address why your Pro Mini's are frying, I've found that the cheap knock-offs that are available on eBay, often can't handle 12V--The regulator fries. An official Arduino Pro Mini can - and so can one's I've gotten from better venders. So, that might be the issue. The Pro Mini can still be used, but you have to supply 5V [connected to the 5V pin].
Other than that, I suppose spikes from the motor might be doing it. jremington's schematic, with the 100nF capacitor across the motor, will likely take care of that.
And, the 180Ω resistor in series with the Gate is a safety feather to mitigate in-rush current due to capacitance on the Gate.
Now, here's the thing about "Logic Level", there's a lot of "difference of opinion", and some of it is mired in rote learning, or from minds unwilling to bend into the creative realm of Amature Electronics.
Have a look at the following Graph:
This is from the IRF520 [Vishay] Datasheet. Notice that with 4.5V on the Gate, the maximum current possible [through the Drain-Source channel] is 1A. And at 5V [the next line up], that jumps to 2A. So, for currents at or below 2A, this MOSFET could be considered "Logic Level" -- as long as what you are driving doesn't need more than 1A [at a VDD of 4.5V] and 2A [at a VDD of 5.0V]. And in the hobbyist world, onee can make sure VDD is at 5V or even at 5.5V for a whopping 3.5A!
Now, there is a Caveat: Let's look at 5V: Notice how the lowest Drain-to-Source voltage is around 1.5V. So, if this MOSFET is driving something at 2A, that's a wattage of 2 * 1.5 = 3W, which is well within the margins on this device, but still, without a heatsink, it's gonna get hot. Also, that's a pretty high "On" voltage. I mean, if you're driving 12V, that's not too bad, but we can do better, if we tighten up the requirements, and shot for more like 1/2 Watt. That would be a max of around 1.1A [the point along the 5V line, where the VDS is 0.45V]. So, within our stricter requirements, this is even more justifiably "Logic Level".
See...most would say, "Dude, it's ridiculous to call this a Logic Level MOSFET, and even more ridiculous to run this thing at only 1A -- I mean, come on! It's designed for more like 6A!!"
And I would say, "If all you got is a lousy IRF520, because that's what came with the kit, then, hey, flaunt convention--if it gets the job done, then why not?!?"
I think the distinction to be made here is: "Fully Logic Level" vs "Partially Logic Level"
OR
Logic Level for Dummies vs Logic Level for Bad A$$ MacGyver Hobbyists!