It's random in a 72 hour window after he is killed but at least 24 hours to respawn, so between 24 and 72 hours after time of death he will spawn again and he will spawn in one of the shourds also random. There is no way to predict it, it was designed that way.

About all you can do is monitor each zone till the weather changes, then you know hes up somewhere, then look for him.

Someone here says at least 48 hours, but I've seen him spawn at 7pm and respawn at 11 pm the next night.