hey Magus, you got some good points. I follow the belief of this:
Magus probably went to 12000 BC for a while to look for Schala. After a while, he probably lost some hope, and asked Crono & company for a ride to 2300 AD, or used magic to send him there. One way he could do this is freeze himself to 2300, or just hitch a ride on Epoch. The Epoch is possible, because Lucca talks to him as a freind in the letter from Chrono Cross. So, assuming he gets there either way, he contacts Belthasar for some help, while Belthasar explains the whole thing {Time Devourer} along with the fact that Schala is part of it. Magus then borrows the Epoch from Lucca to work as a helper for Belthasar so he could help his sister {stepsister?}. Magus could then use the old Epoch to look after the parts of Project Kid, and return back to 2300 in order to get more details from Belthasar and to stay close to him in case of a FATE memory wipe.