ToME WikiThe Maze is a both a regular side-dungeon and the site of a quest.
Contents
The dungeon
The Maze spans dungeon levels 25 to 37.
The dungeon is a weird one. You cannot keep track of where you have been in the maze. Some perception-type spells will temporarily show locations of doors, stairs, monsters, etc, but they will not remain visible on the map. (Hint: A good memory helps!) The map size is not all that large, but do not presume that a single detection spell will span the entire level.
Traps detected with trap detection spells will remain "spotted" once you are in view of the relevant square.
The passages are all one-square wide and twist and turn in, well, a maze! Walls are diggable -- and digging is very useful in this dungeon, so bring a good digger or some Wands of Dig. You can teleport. Another good way to navigate in this dungeon is to make use of light spells, wands or rods to tag the places you have been before. Probability travel will work!
The Maze is well known for being a good place to find stat-gain potions, second only to the worm lair at level 25+.
Monsters
Hounds, assorted Orcs/Trolls, some spellcasters. A number of midlevel uniques often show up in the Maze if you haven't killed them already; Gorbag and Lokkak come to mind.
Boss
The Minotaur of the Labyrinth guards DL37 of the Maze. He drops the Steel Helm of Hammerhand, which activates for berserk (Useful for turning spell points into hit points).
The quest
Obtaining the quest
Speak to Melinda Proudfoot in the town of Bree. She will tell you that she is looking for her son, Merton, last seen playing near the Maze.
Performing the quest
While in the maze, you look for Merton (a purple 'h'). He's got a broken leg and needs help getting out of the Maze. When you find him, give him a Scroll of Word of Recall (make sure to carry many, one for him; one for you; three for fire breath attacks or better yet fireproof them. Meeting Merton without a scroll is frustrating).
There is a chance of Merton being generated on each level of the Maze with the exception of the top and bottom levels of the Maze. You don't need to avoid shafts and do each level carefully, none of the levels who can have Merton is "special" in any way; it's just random. No towns.
Your greatest ally in this quest is a something of telepathy or very frequent use of sense monsters type spells or effects (rods of detection and one artifact helm comes to mind). Mindcrafting level one has "sense monster's minds" for that, and Merton is not as mindless as he sounds.
Your need a way to dig walls (or skip them) to get to Merton once spotted.
Another great ally is your ability to use teleport level, probability travel, deathmold's ability to travel up and down levels, and maybe a large pile of teleport scrolls if your detect monsters range is small. You don't need to search ALL of EACH level, just cover as much ground as you can per minute.
You can't fail this quest. Merton might be foolish, but as a Hobbit he's very lucky not to get killed and can be generated again and again until rescued.
The quest reward
After Merton WOR's out, you can go about your business. When you get around to it, go back to Bree and speak to Melinda Proudfoot again. She will reward you with a Rod Tip of Recall. Very handy!
Chatter
MayLith: I took the 'you can't fail this quest' advice to heart, and I have to say that I have never, ever been more frustrated with this quest since I did that! How often does Merton get generated? Does the level he's going to be created on get fixed on character creation, or does he have a chance of being generated each time you go up or down a stair, or what? (*sounds of me bashing my head against the table*)
SimonSorc: it's purely random, nothing fixed. If you have telepathy, you can just go up and down some stairs in the middle levels and you'll eventually spot a purple 'h' that isn't a mindflayer.
MayLith: Gah, I was afraid of that. My archer's got full telepathy (thanks to an amulet) plus Mindcraft Precog to take care of non-telepathy-sensed things (and I know Merton's not one of those, btw).... but I've been scumming stairs in the Maze for agesh now. She's CL30, for pity's sake! Rrrrrggghhh... The RNG must not like her. Anyway, thanks. 
GreyCat: I've got my doubts about the "purely random" part too. I haven't checked the code, but with my current character I went up and down and up and down and ... in the maze for a very long time without finding Merton. Then I left to do a god quest, came back (with full telepathy), but this time I started at the top and walked down. I found Merton on the second level. So I have a funny feeling that the level he's going to be generated on is fixed at birth/quest-getting.
NeilStevens: Yes, that was misinformation, at least according to my experience. I've always found that Merton stays on the same level.
DarkGod: Merton's level is choosen at game start, once ste it will never change for this character.
vfb: One more note: if you don't talk to Melinda in town first, you'll never meet Merton.