The remains of Menamon are located on the first floor, through the hallway that contains the poisonous mist, in a room with two torturers. The parts of the body are scattered throughout the room. As of 7/6/2008 they do not have the blue accent denoting where they are.
The scalp is the hardest piece to find. It is against the opposite wall that you face when you first walk into the room.