I found this article on Project 1999...
https://wiki.project1999.com/An_Undead_Cyclops
I'm not 100% sold on the coordinates either there or here, but I can say that they may have been on to something regarding the various elephants as placeholders.
It was impossible to not run into this NPC while hunting elephants for my alt's ancestral armor quest (three alts did this actually), usually wandering in by the hermit hut.
But, no sign of it or the other cyclops anywhere in the zone for hours searching with my main.
Sure enough, after the first few elephants went down, the cyclops (the live one) finally showed up on the edge of my view north of the hermit hut and I caught up with him up by the gnolls. On a later attempt, I saw him wandering in from the aviarks, south of the hermit hut, near the coordinates given for the spawn of the undead one above. It stands to reason that the live one is the immediate placeholder for the undead one. In my case, after a little bit (10 min maybe, I wasn't counting) I finally caught the undead one by the aviarks.
So, my suggestions for anyone hunting this NPC:
1) Work in a triangle between aviarks, gnolls, and hermit hut.
2) Kill every elephant you see, and if you run out start dropping lions (definite placeholder for elephants, based on past experience).
3) The live cyclops will spawn first (again, appears to path by the hut), then you should expect to see the undead one (probably at or near the aviarks) a few minutes later.