The quest comments on Wowhead indicate many have tried and have had trouble with the NPC bat. Since the questline was setup before the events of the Battle of Lordaeron, you could first visit Zidormi and go back in time when the area wasn’t blighted.
Make sure you are entering the tunnel to the West of the city (sewers). a little more than halfway down the main tunnel, a man-way will open on the right. Take this until you enter the main area. Once there, you make a hard right, continue toward the Apothecarium, and you will enter a phased scenario. Through a door, down a ramp to a medium sized room (through a couple of mobs). On the left side of the medium sized room you will find Koltira. Kill the elite that spawns, free him, and wait for him to create a deathgate.
Good luck!