Why not float instead of run... right?
It's probably the manipulation of the space time around them, like Zeality stated. Their magic field may in fact allow them to control the gravity around them. That's what I don't understand about the character Guile in CC. He is the only character that's floats above the ground...
About the time gate being sealed by Schala, he made her do this most likely to conceal his power. If Magus did choose to use his power, which he DID refrain from using during his stay in Zeal, his cover would've been blown. Schala and/or the Queen or any other Zealian may have felt the same presence of the magic aura of Magus. Magus's cat can put two and two together and can sense the familiar presence, depicted in "What the Prophet Seeks . . ." and after the Zeal disaster when history repeated itself.