most probably overvoltage at the gate, try adding a 4v7 zener.
Atmega cannot output more than 5V. I think that Atmega has too weak output to charge/discharge gate capacitance fast enough. So at such PWM frequency mosfet stays in linear range big portion of time, exceeds safe operation area and fails. Use proper MOSFET driver IC or make driver from discrete components.
There are basically only two failure modes of a MOSFET, thermal overstress and Vgs overvoltage. Modern MOSFETs can handle Vds overvoltage well, they simply avalanche and act as a zener diode. However, this can again lead to thermal overstress.
Your oscilloscope shots seem to show the motor running in steady state, right? Parasitic effects will exaggerate at higher currents, I would go to the extreme there and drive a blocked motor for a short time, and check the waveforms (and the MOSFET temperature rise) then.
EDIT: how is your 12V supply bypassed right on the freewheeling diode? You need low ESR capacitors with substantial capacitance there, the freewheeling current must have a good (AC) return path to ground. I suggest to monitor the 12V on a scope with that blocked motor as well.