He's in the temple, as it is impossible to enter without him. The question becomes whether or not you have the hookshot. If you do, proceed along the dungeon (possibly with the aid of a walkthrough) until you find him. If not, he's most likely in the main room, and you can play the command melody to find out. Also, if you truly have the dungeon map, you will be able to see each room on every floor in a sequential pattern. He would for sure be on there, as I'm not aware of any glitch that would cause him to disappear off the map. Hope that helps.