How could he recover ?
The "recovery" is not that clear, he did not go back to the level of support he had in january. At some point people spoke about him stepping down, but the support in the polls for him (or the replacement right-wing candidate) never went very low, as shown by your graph.
Could it have to do with the rise on the polls of Mélenchon, making some conservatives fear him and decide to go for Fillon?
This would not be a rational approach. Indeed, Fillon is predicted to lose against Mélenchon in a second round. The only candidate who is predicted to win a second round against Mélenchon is Macron.
As for why he still has support, this becomes more of a subjective question.
One reason can be the support for his ultra-liberal agenda. He did call for French people to support him, not to love him, which was a change in attitude. And he is still the candidate of an important party.
Another one can be the importance of the fraud he is accused of. Some other financial scandals concerning french politicians were to another level. We can compare his affairs (giving fake jobs to his wife and kids) to those of the 2012 right-wing candidate, Mr Sarkozy (money taken on sub-marine sale to Pakistan, Khadafi supposedly founding his 2007 campaign, taking advantage of an old rich woman, ...). Both the amount of money involved and the "moral context" are quite different. Reading the traditionnal press, one can infer that traditionally right-wing voters, while disappointed, are willing to forgive him.
As pointed out in the other answer, his age compared to the one of Macron could also be one explanation.
Regarding the support of the catholic population, I wouldn't bet on it. According to this article, only 5 % of French people regularly go to a mass, while about half claim to be catholic (less than half according to the latest estimates, 53 % in this article from a Catholic journal). Among those "catholics", 6% of them did take part in the anti-gay wedding demonstrations ("manif pour tous"), 73% did not want to take part in it. You don't get among them the 19 % of vote intentions of the polls. While Fillon brags about being fervent, this does not look like it has a big influence on his voters, for the simple reason that French people don't care that much about religiosity when it comes to politics.