I just killed her north of Deadbone Reef. I had killed a few undead sailors a few minutes prior and killed nothing afterward. After a bit of time the sailors repopped on track, and then a few minutes later a great white shark appeared on track. In the 10 minutes after the shark showed up, nothing else did (apart from the transport ships).
After killing the shark, a goblin spirit caller came on track. The goblin spirit caller was followed by a goblin shaman.