replace mega16U2 on Mega2560

"Any tips on soldering with a heat gun?"
You really need a nozzle to control airflow.
Such as
http://www.mpja.com/prodinfo.asp?number=15284+TL
or similarly sized for the part you are trying to rework.