This level is on the small side: it consists of a few areas arranged around a large central room. You begin in a small outbuilding next to a lava-filled area with a pathway of ice crossing over to the far side. Cross over and enter the door on the far side. In here is the very large central room, with a floor made of ice. Taking up most of the space in here is this level's namesake feature, the labyrinth.
The labyrinth is very creatively designed: it's a grid of square sections, with the pathways at irregular heights. The pathways are defined and progress impeded by having the ceiling levels of the surrounding areas too low to get under, but this allows you to see everything and for enemies to infest the area. Thoroughly explore the labyrinth; there are many, many items available here. Try following the right-hand or left-hand wall and you'll cover everything. In approximately the center of the labyrinth you'll find the Yellow Key.
In the other three corners of this central area are the Yellow, Green and Blue Doors. You'll also see decorative panels in the corners. Once you've opened a corner's door and entered that area, whenever you step out of or back into that small side area where the door is, the panel in that side's corner will momentarily open. An item will be inside. Also, try activating those large decorative panels between the torches. One is a hidden door that looks over one of the areas you'll get to later. It'll be barred off just inside the panel, but you can clear out most of the enemies inside, plus there are items behind the panel.
Open the Yellow Door and enter that side's area. You'll see a Dragon Claw out of reach on a shelf just ahead. You'll get this shortly. Outside, through either wooden door, you'll also find Wings of Wrath. (These are the only ones in the level, but you won't miss out on anything later if you want to use them up ahead.) The two exits from this room go to either end of a loop pathway surrounding a very large iced-over outdoor area with pools of icky water here and there. In the center of this area is a structure capped hy a rock formation. First, look along the outside of the loop path for a side passage. A door ahead will open, going back to the lava/ice area where you began the level, and there's an item in that small cave to the side.
Jump down into the iced-over area. After clearing out the enemies, look for and run to the door in the center structure. Inside here is the Green Key and a teleporter. Get the key and take the teleporter, which goes to that shelf with the Dragon Claw. (Amusingly, sometimes an enemy in here will walk into the teleporter and be sent to the shelf. There's nowhere for it to go there, so when you teleport there, the enemy will be telefragged.)
Green and blue
Now that you have the Green Key, go to and enter the Green Door. Look for two stairways leading down. The left side is a dead end for now. Go down the right side and explore inside all of the rooms you'll find here. The large door around back goes to a room with the Blue Key, a teleporter and side rooms on either side, visible through windows. The two small doors in the hall go to the left-hand rooms. The teleporter goes to the right-hand room, where there's a weapon and items. In here, activate the wall with the gray texture to open a door going back to the middle room.
Collect the Blue Key, go back out the wide door and turn left. When you picked up the key, a door here opened, revealing a new area that goes back to the left-side stairway. Take the door in here: this way goes around and up, through a hidden door that opens, and back to just inside the Green Door. You'll find the Map Scroll along the way. (Earlier you probably saw a gap near the ceiling in this wall that opened, and the passage beyond on the automap.) Don't leave yet: go left and back over to where the two stairways are. A door in the outer wall has opened, revealing a short passage leading back to the lava/ice area near the outbuilding. Look along the left-side wall for a lighter section on the floor and ceiling. This part is a hidden door to a secret area in the back of the outbuilding, with a Phoenix Rod inside.
Go to and open the Blue Door, go down into the tall room inside, and hit the switch in the nook at the far end. This opens a door in the lower half of the stained-glass window in the room. The exit portal is inside.