I've beaten the maze after hours of wandering around; the problem with it is that you can't really give directions because places don't stay put. A few things are persistent, though. The first thing you have to do is to get your sword back from the goblin base. No sword = no chance of escape. After that, you should get to what I call the 'market maze' which for me was ALWAYS on the far right of the caves. There are a few things to do in there. You can help the cowgirl Rosa by bringing her escaped slaves and she pays you for them, there are the slime caves where you can either help the slaves and escape with them or you can either help Rosa capture their leader, or help a succubus capture them all.
There is a location in the 'market maze' called The Slave Market. In here, you get the option to return escaped slaves for money, succubus milk, and Lokka loyalty.
You will not beat the maze without helping Rosa or the succubus slaver, at least a little. You need plenty of money to buy healing supplies and grease foe the slime caves, because no matter who you side with, you have to kill a slime boss and the enemies it summons into the battle. If you try to fight slimes without the grease, you will die because they take nearly no damage without it.
I can't really give you directions because of the nature of the maze, but after exploring enough you'll kind of get a feel for the direction of everything.