How can this MOSFET become overheated? How big should the heatsink be?
I calculate 7.5W worst case with Rload =3 and Ron = .2 

I = 6.125A. 

That squared *.2R = 7.5W. 

Yes that is way too high for a bare To220. At 83.3C/W channel to ambient of the device that's a whopping 625C temperature rise.. So it is going to melt.

You could add a whopping heat sink, but really, you need to find a different MOSFET that has an on resistance in the milliohm range.