I think I want to make it deadly enough that they run from and hide and it becomes an ongoing threat, or the PCs try to get allies to fight it. Note that I boosted the Misty Step from the normal 30' to 60'. That's going to get it out of range of melee fighters very fast.Nice. I'll use that. I was going to make him teleport as a bonus action so that when he first sees them he will teleport behind them and attack from the back. I'll also play him as highly intelligent (but still savage), so he will recognise the weakest characters and make use of opportunities. If he looks like being defeated he will get the heck away and then start stalking the party once he has healed (if they are still in Omu).
EDIT- And that bonus 30 feet might be TOO good. I'll have to see. Or I could give it limited super steps. Maybe 2 or 3 per short rest, and the rest of the time it is 30'.