Melvin was the last man to stand with God against the Demon Lord and he was sealed away by God before God was defeated. He's definetly someone you want on your side. After you complted Dharma, you could've gotten this fake magic carpet from this idiot called Nicola. After getting the MermMoon in Hamelia, you can prove yourself to be someone great and deserving of the real carpet to go unseal the Great Hero, Melvin. Show Nicola's maid the MermMoon and she'll exchange it for a Flying Carpet. You must try out the fake carpet first though, so you can bitch that it;s fake. Follow the maid behind the temple and search around until you find a staircase; it'll lead to the magic carpet. Use the carpet on Mezar island to get to that little cave to talk to a Soldier of God. You'll also get a WindShard there.

It just so happens that the stone Melvin was sealed in is Hondara's HotStone. Go see him in the Estard Bar and you'll find out he sold it to Brugeo, the eccentric rich dude with mansions everywhere. Go to the one next to Orph then to the one in Litorud, then to the one in Krage and you'll find him back at the one in Orph. Brugeo will decline your request for the HotStone at first, but as you exit his Orph mansion, he'll join your party.Before you leave his house, however, be sure to grab the LandShard in his basement.

Go to the tower west of the Medal King Castle (north west fo Hamelia) to get to Melvin. The tower's tall and it takes a while to get to the top, but it's very easy and the monsters are easier than the ones in Gracos' lair. Melvin will join your party and bring a FireShard when you release him. You'll want to change his class at Dharma and give him some decent fighting equipment. With the flying carpet , you can go to the Sphinx and get an AquaShard in it.