Telepathy I get, but so what about her being an "elder of the universe" (whatever that means, since I know she's not listed among the ranks of the Grandmaster and the Champion and them)? She's an elder of the wrong universe to know that red suns reduce Kryptonians to roughly human-level abilities. Plus, there's no guarantee that that would even work on Superman Prime. He had some weird gold coating when he appeared; that might protect him from his old weaknesses. He's also grown in power right in the present-day comics to the point that Kryptonite does virtually nothing against him already.
I'm not saying Superman Prime could beat Phoenix. My point is actually that it's a bad contest from the get-go because we simply don't know a lot about Superman Prime. He appeared for a handful of pages in the DC One Million mini-series. For all we know, he has no weaknesses, he's developed super-telepathy, and he's now a tenth-level adept at super-magic. All we know is that he came out of the sun powerful enough to awe the other heroes present; there's simply not enough information on him for us to quantify how powerful he really was or measure that against the Phoenix's level of power.