This is probably the stupidest part of the game. You can't find the mage until you're level 13-15. In order to get to level 13, you need to get in the barrier.
Now, if you talk to the imp at the End of Time he'll tell you to kill the two mushrooms and the barrier will go down. That's true, but if you don't want to kill them, you have to find the scroll.
You'll find the scroll buried up on a hill covered in traps. To find the hill, go to where the nectar drunk goblins were and head west (you can't miss it).