take him to the back of the cave and tell him he is there. this was the only part of the entire game i couldn't do without a hint. wasted a hour or so on it too. i'm curious if you could bring him to Mora Sul as a gift for Gonzales?
The slave to get for Gonzales is a woman on the oases north west of the city, you can buy her for 300 gold. As far as I know, no other slave will do - he's only interested in women.
I left him waiting, as he continued to follow me even after taking him to the back of the cave and having a dialogue. There were no other options. Now every time I teleport, I get a slave still waiting message!!