UPDATE:
Having finally traced down a searchable text of the [majority of the] Zohar, I can confidently say that it DOES NOT seem to reference the phrase "Ahavat Chinam" in Hebrew at all, and certainly not in contrast to "Sinat Chinam." [Though it may be in the few still-unavailable volumes in Devarim.] Thus, the earliest traceable reference to this issue is the Pele Yoetz's 1824 discussion of Ahavah being a tikkun for Sinas Chinam, in contrast to the Alshich's focus on eliminating jealousy as a cure of S"Ch. The Darash Moshe (1912 or earlier) seems to be the first to specifically refer to the concept of Ahavas Chinam.
I've traced it to a possuk in Yishayahu (52:3) where the medrash seems derived from.
The Pele Yo'etz references this as well in "Sin'ah" and talks about Sinas Chinam and the tikkun of ahavah in general (and particularly for one's wife), pushing the earliest mention to 1824, but he does not use the explicit phrase of Ahavas Chinam. He identifies the source vaguely as RaZa"L, indicating that this concept either stems from a well known specific source of multiple origins (possibly lost to us) or well known "folk knowledge" - that it was a popular concept in circulation without specific attribution.
Oddly enough, the possuk in Yishayahu DOES come up in the gemara in Sanhedrin 97b, but it's interpreted differently there. This source from 1895 apparently places it in Zohar on Va'Eschanan, though it provides a different page number (267).
Multiple sources in the late 1800's hone in on the Sinas Chinam aspect, which they attribute to the Alshich, but state that the source is primarly economic jealousy, so they avoid the "Ahavas Chinam" route.
Here's another source from the Imrei Fi in 1930 as well. That two sources (one in Poland and the other in Isreal, no less) in the same year use a similar term implies it was in use earlier.
Here's one from Ma'agalei Tzedek (Munkatch) in 1884, but it's specifically in reference to Hashem rather than an antidote to Sinat Chinam.
Same with this Haggadah (Mareh Yechezkel) from 1894, whose original printing is from 1879.
The earliest source of the phrase I've found is 1838 from the Mata'ei Moshe, but again, this is reference to Ahavas Hashem.
The Darash Moshe in his Chidushei Aggados on Sanhedrin (in 1912, but since this is a compilation of sefarim it was probably written much earlier) brings down an interesting midrash that's related; "I sold them (Yisroel) for Free/Chinam" - because of Sinas Chinam, "And they will be redeemed for Free/Chinam" - that is when the Tzadikim love one another also freely.
I was able to trace this down to a Midrash Tanchumah in Devarim, but the exact text has to do with a discussion on Hashem "selling" Israel into golus, so it seems that the Darash Moshe is engaging in some form of poetic embellishment (possibly based upon the Pele Yoetz?), though he does reference the Zohar.