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.
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.