The Cleric is still at risk of being petrified
There was a clarification on a similar question like this by Jeremy Crawford, the 5e lead rules designer.
Q: Truesight lets you pierce/nullify illusion effects like the ones create by Phantasmal Force (in the mind of a creature) & Mental Prison (the target to perceive itself as being surrounded)? These spells are considered visual illusions for the purpose of Truesight?
A: A visible illusion is something illusory that you can see with your eyes. If an illusion is perceived only within someone's mind, that's not a visible illusion, even if the person thinks they're seeing it.
Unlike a spell like minor illusion, whatever phantasmal image the cleric thinks that they see is not actually manifested in reality 1. That is, there is no visible obstruction between the medusa's eyes and the cleric's eyes. The cleric might believe with all of their being that the wall exists, but nobody else can see it; it's effectively a hallucination.
Because of that, the cleric is still technically able to see the medusa's eyes. So if the cleric is in range, they would need to make the saving throw despite the fact that the cleric doesn't think that they can see the medusa's eyes. The effect of Phantasmal Force would then force the cleric to rationalize why she still had to save against the medusa's gaze, even though there is a wall between them.
The cleric and the medusa can technically see each other, but the cleric doesn't believe that she can see anything past the hallucinatory wall. However, belief does not equal reality. So, since they can see each other, the cleric would have to make the save.
1. By "manifested in reality" I mean that nobody else can see the illusion. There is no "magically bending light to create an image of an object at a location" or however you like to explain lower level illusions.