DISCLAIMER WARNING: I HAVE ONLY SECOND HAND KNOWLEDGE ABOUT THE SUBJECT I AM ABOUT TO SPEAK.
As far as I know, most outsider and elemental races are FAR older than any humanoids of the material plane. Or at least they are talked about more. Based on certain readings the eldest outsiders are likely older than the Gods too - but then who created the planes? Most pantheons have the gods doing that and so it could be a wash. But my thought, which is supported by actual writings as far as I know, would say that outsiders are far older and so using that, let me get onto your specific questions.
Q1: At what point in the history of the Planescape Great Wheel cosmology did the Janni genies appear on the Prime?
I think that this one is hard if not impossible to say because it depends on each individual settings/worlds. As far as when Janni could have first been formed? That could have been any time (if I'm reading their description correctly) in fact the further back you go the more likely it could have happened since all elementals were under one authority and so I would expect more inbreeding.
Q2: Is there anything in canon to indicate this?
If there is, someone else will have to give it to you. Sorry. I have nearly NO actual planescape books, even though it interests me. In many cases though even sources that could have given you this information won't have it. There is research, mostly into fanon, that could answer these kinds of questions more definitely but as far as I know there is likely zero canon answers to indicate this kind of this specifically.
Q3: Did they predate mortal flesh and blood Prime races like humans and elves?
Based on what I said above; hard to impossible to say. It depends on how and when they first showed up. Most genies do predate flesh and blood races. Or at least predate the discovery of the planar powers of such creatures.
Q4: How and why did they come to be, and was there a Power involved?
Assuming you mean Janni: Unknown (others may provide a definite answer).
I'm basing what I told you on several sources. One of the most cohesive as far as 3e goes is the following link. That doesn't mean it is most accurate as far as
Planescape goes, but as far as I understand Planescape was mostly written (almost entirely?) in the 2e days so there were some alterations to make it fit and Rip does one of the best jobs of pounding odd bits into place that I've ever seen.
Link:
http://community.wizards.com/go/thread/view/75882/19558750/The_History_of_the_Lower_Planes,_revised