If you kill the 3 leaders before finding him, he escape by himself and you find him at the grove later like you did.
Halsin is inside the temple, but you need to use a door-transition to get to the prison floor. That door is "guarded" 3 goblins who stand in the room beside the one where Minthara (the drow lady) is.
