Augustine of Hippo is basically universally credited with the coinage of the phrase. It is an idea which can easily be supported by the Bible, but he was the first to say it in a form close to its present proverbial form. He probably didn't think he was coining a cliche, since it was neatly hidden away in a letter to a convent. This blog has a summary of the circumstances:
Let’s establish this point from the outset: St. Augustine more or less
coined the phrase “love the sinner but hate the sin” as a description
of how Christians should behave in the church discipline process. He’s
(apparently) talking about about those man-chasing “cougar” nuns that
like to flirt with men and can’t keep their naughty bits covered. It’s
hard to believe that this was a serious problem in 424AD, but – in
respect of his sainthood and all that – we’ll give St. Augustine the
benefit of the doubt.
In an attempt to better describe the love and wrath of God, the modern
Christian cliche “love the sinner, hate the sin” has emerged in an
attempt to capture the often-perplexing paradox of how God can
simultaneously demonstrate wrath and love for mankind. There are hints
of Biblical truth within the cliche. In His perfect holiness and
justice, God is opposed to the open rebellion of sin (Romans 1:18-32).
Yet, God loved us while we were still sinners and the enemies of God,
and sent His only Son, Jesus Christ, to pay the price for our sin
(John 3:16; 1 John 4:7-21).
The full text of the letter can be found here. Augustine opens it by saying:
As severity [i.e. hatred of sin] is ready to punish the faults which
it may discover, so charity [i.e. love of the sinner] is reluctant
to discover the faults which it must punish.
And later he says:
Moreover, what I have now said in regard to abstaining from wanton
looks should be carefully observed, with due love for the persons
and hatred of the sin (cum dilectione hominum et odio vitiorum),
in observing, forbidding, reporting, proving, and punishing of all
Cliches and proverbs always evolve and mutate. We see in Augustine the pithiness and the exact idea expressed in the cliche. But nobody seems to know exactly how or when it entered English in its exact present form. On the English Stack Exchange one answer notes that it seems to have coalesced and "started appearing everywhere" in the 1820s. Others have found other mentions in the 18th century.
For example, in 1729, the hymnist Isaac Watts wrote in an essay, "[Jesus] hated even the least sin, but loved and saved the greatest of sinners." Similarly, in 1784, William Mason wrote in his commentary on The Pilgrim's Progress, "[God] can love the sinner, as much as he loaths his sin." And the 1779 Charles Wesley hymn Equip Me for the War says, "O may I learn the art / With meekness to reprove; / To hate the sin with all my heart, / But still the sinner love." Internet sources indicate that the idea became more well-known when Gandhi referenced it in his 1927 autobiography: "'Hate the sin and not the sinner' is a precept which, though easy enough to understand, is rarely practiced, and that is why the poison of hatred spreads in the world."
In summary, it was first said by Augustine, echoed (coincidentally or not) by Christian writers in English in the 1700s, and it became a proverb in the 1820s for whatever reason. Then in 1927 it became even more popular when Gandhi used it.