I know its been explained, but I am still not clear how it is part of 616 pre-history...
I'm not sure if you're asking "How" as in, "What justifies the claim" or "How" as in, "where does he fit between other events", so I'll answer both. Again, neither to me justifies his inclusion in this
project, but I'm all for the proliferation of knowledge however arbitrary.
Anyway, the answer to why
he is considered part of Earth-616 is really "just because". Either for promotional reasons or just to add to the richness of the Marvel U, he has been situated as part of it in various publications from official handbooks to things like Marvel Saga
(Which, btw could be a good resource for readers having trouble with the early Marvel stories).
As to where
he fits, it's sometime after the earliest events concerning the Eternals/Deviants/Inhumans/Sinking of Atlantis and before everything else.