I've been looking for this guy for months. I would pop in and run around the zone checking tracking to see if he was up. He never was. Yesterday, I decided to look in earnest. Put some effort into it.
Based on the advice of Duchess Cylius' post below, I went to the far SW corner of the zone. I killed everything that showed up on track (except the Sea Monster). For two days, I've killed Sea Turtles, Goblin Shamans, Goblin Marauders, and various Sharks. Lots and lots. But no spawn.
Then, for no apparent reason, I noticed that Sea Snakes were showing up on track. After I killed three Sea Snakes, a Goblin Fisher showed up on track (still in the far SW corner of the zone). I killed the Goblin Fisher, and Teragadon spawned immediately at -4623.56, 4366.36, 216.27. He was amiable to me. Once he started attacking I noticed that he was hitting my WAR Merc for 800-1400 hp, which is really unusual for this zone. He kept casting Shredding Bite on both me and the Merc.
At 50% health, he warped. Luckily, he was still being tracked. I found him at the NE corner of Stormscape Island (in the water) at -3205.12, -24.96, now at 100% health. This time, the Merc took him down pretty quickly. He dropped Sea Tear, Shark Eye, Shark Fin, and Shark Cartlidge.
Bottom line.... go to the SW corner of the map and kill everything.
Praise Tunare!
Drudarn Canbakeit
87 Druid
The Rathe (Prexus)