You are asked to deliver a letter to Kwi'the Il'zhe in Maj'Dul ( 122, 139, -26 ) /waypoint 122, 139, -26. To get to him, take the carpet ride from the docks. When you hail him, he will attack. The quest will update after you kill him. Also, he may cast Ice Comet, which causes quite a bit of damage.