Seconding @Aryeh that this is an excellent question. I did some research on the subject and this is what I've found on the matter:
Authorship:
First of all, it seems that the composer of this non-verse is, sadly, unknown. The only source I've currently found who attempts a suggestion on the author's identity is from Rabbi Tzvi Elimelech Shapira of Dinov in his book Regel Yesharah, pg. 207, where he states that it was composed by the Men of the Great Assembly. Personally, though, as I have yet to find any other source stating this, and not even the Yaavetz states this, I believe this was the Rebbe of Dinov's own idea, based on how anonymous prayers are generally attested to the Great Assembly. The idea in itself is not entirely implausible, given how ancient this non-verse is (see below), but the fact that other sources are silent makes it more questionable.
The composition of the non-verse:
Prof. Yehudah Ratzhabi in his essay "סדר רחמין מתקופת הגאונים לעשרת ימי תשובה", Sefer Aviad, pg. 317-369, writes that he believes that the oldest manuscript of Selichot we currently have is MS Heb. e.69 and Heb. d.68 (the manuscript fell apart and was accidently put into separate folders), dating to before Rasag's time (!). In e.69/54b, the nusach of the verse is:
"זכור ה' חרפת ירוש'"
Prof. Ratzhabi explained that Selichot during that time weren't as organized as they are today, with no properly-set nusach. At the time they were called "Rachamin" and were made of a mixture of piyutim, verses, verse targums, verse "embellishments" (e.g., הביטה ענינו ה' אלוקינו instead of הביטה ענני ה' אלוקי (Tehillim 13:4) and folk-compositions.
This particular manuscript, according to notations left by the scribe, was copied from the community's main siddur. This Seder Rachamin was essentially a collection of suggestions of things to say. Many of the Rachamin are written in shorthand because at the time most people remembered all of the lines and verses by heart, or could at least complete when given the first couple of words. Anything that one might happen to not remember could be checked in the main siddur.
Therefore, this line probably was not just short for "זכור ה' חרפת ירושלם" but for the entire non-verse (i.e., the shortening of ירושלם signified more than just that word).
The question is, what's the original version: "חרפת ירושלם" or "חבת ירושלם"?
To that extent, I examined a number of manuscripts. There are six Genizah MSS with variants of this non-verse. Variants (including extra letters) are underlined:
As can be seen, there's only one MS with "חבת" in it, in full spelling: "חיבת". According to the Genizah catalogue, this MS is that of Italian nusach selichot that were found in the Genizah. Though not dated, I believe that the MS is significantly less older than most Genizah MSS, because the script style looks almost modern:
As opposed to this Italian MS, Parma 3536, dated to 1297:
If anyone is more knowledgeable on dating script styles, I'd be happy to hear more info.
Therefore, I believe that the Italian MS is not evidence that the original was "חבת" and not "חרפת".
So far, the other oldest European MS that I've found that have this verse are Harley MS 7618, f58v, an Ashkenaz (Germanic) nusach:
thought to be dated to somewhere in the 13th century, Harley MS 5701, f074r, also an Ashkenaz (Germanic) nusach:
thought to be dated from the 13th-early 14th century, and Machzor Worms (Ashkenaz), vol. 2, pg. 146:
dated to 1280.
In short, we have four European MSS (three Ashkenazi and one Italian) from the 13th-14th centuries that attest that in Europe, the version was "חיבת ירושלם". In all likelihood, it was from here that it evolved into the modern version used by Ashkenazim "זכור ה' חבת ירושלם אהבת ציון אל תשכח לנצח" (the Yod in חבת was taken out).
However, most Genizah MSS attest to "חרפת ירושלם", which leads me to believe that this was the original version, while a later European Jew wanted to make the two parts of the non-verse parallel one another (as can be found both in many Tanachic verses and in many lines in piyutim and songs) and changed "חרפת" to "חבת", to match the "אהבת" part.
Though to us it seems that חבת would make more sense as the original version of the verse, there's actually at least some sense to חרפת. Prof. Ratzhabi explained in the above-mentioned essay that many of the Rachamin of d.68-e.69 mention decrees against the Jews, some having been thwarted, but perhaps not all. As there are similarities between some of the decrees and decrees set against the Yemenite Jews over the centuries, and the scribal notations are in Arabic (but none of the Rachamin themselves), it seems that the חרפה mentioned here may be a reference to fairly-recent (to the time of the composition) events that happened in Yerushalayim. Consider that the Temple Mount was not a place significant to Christians, so it was mostly left alone by them. However, the Arab Conquest of Israel changed the status of the Mount, as it was deemed holy by them as well, which led to the building of mosques on it (see here). This was a great tragedy, which may be what is referenced here. If it's as ancient as the Rebbe of Dinov wrote it was, then perhaps it came from a now-lost text and was dusted off and placed in the Rachamin, because of said-recent events.
Now, you might have noticed that some of the European versions feature an extra Vav before "אהבת ציון", forming "ואהבת ציון". As most MSS don't have the extra Vav, and none of the Genizah ones either, I'd guess that the original version didn't have a Vav and adding the Vav was probably later scribal error.
Another variant is a change from "אל תשכח לנצח" to "אל תזנח לנצח". It is difficult to tell which version is older. The oldest dated MS, as we saw, is only a short-form of the non-verse and doesn't have this section.
Lastly, ENA 1968.22 says "זכור ה' חרפת עבדיך אהבת ציון אל תשכח לנצח". In some MSS, the verse "זכור ה' חרפת עבדיך שאתי בחיקי כל רבים עמים" (Tehillim 89:51) appears directly preceding this non-verse (though I believe it is no longer said in any modern nusach), so I think that in this MS's case, the scribe accidently skipped part of both lines, merging the verse with the non-verse.
The Tanachic roots of the verse:
As to what verses it might be based on, Dov Sadan wrote an essay on the subject of this non-verse - "פכים קטנים, ד. חיבת ירושלים ואהבת ציון", Sinai 87, pg. 282-287 and brought several suggestions for the Tanachic roots of the verse:
"זכור ה'" (Tehillim 132:1; Tehillim 137:7; Eicha 5:1), "אל תשכח" (Tehillim 10:12; Tehillim 74:19) and the Genizah variant "אל תזנח לנצח" (Tehillim 74:1-3; Tehillim 44:24) and similar phrasing in Tehillim 9:19; Eicha 5:20; Amos 8:7.
Sadan, though apparently unaware of the Genizah variant of "אל תזנח לנצח...", thought that this was the original ending of the non-verse. It's possible, though as I said, it's difficult to know which one is older.
Other verse suggestions were brought in the book Areshet Sefateinu, pg. 265.
Lastly, Prof. Nachum Meir Bronznick in his book "פיוטי ייני - ביאורים ופירושים", vol. 2, pg. 22, wrote that he thinks this non-verse was based on "יבחר לנו את נחלתנו את גאון יעקב אשר אהב סלה" (Tehillim 47:5), however he writes this based on the "חבת" version and makes no mention of the "חרפת" version. He finds parallels between סלה and נצח and suggests there's evidence that Eretz Yisrael is sometimes known as Yerushalayim.
What is it doing among real verses?
As Prof. Ratzhabi explained, there were different types of Rachamin, but no set nusach. Some Rachamin were entirely blocks of verses, some were entirely non-verse piyutim and some were mixtures. As we can see from the older Genizah MSS, this non-verse was originally part of a section that was a mixture. It seems that at some point, the זכור ה' verses and non-verses were set apart, forming a new Rachamin. From there it eventually became part of the Ashkenazi Vidui.
Though Rabbi Dr. Heinemann, as brought by @Argon (see here), thought it was inserted to even up the numbers of זכור verses, I don't believe this was the case, because זכור verses as standalone sections were comprised of varying numbers of verses (compare different MSS and nusachim) - 2, 4, 6, etc. Moreover, we see that it wasn't originally part of a זכור-only section in the early Gaonic period. A זכור section first appears in the mid-Gaonic period, in Seder Rav Amram Gaon:
And a זכור section also appears in the slightly-later Siddur Rasag. A variant of the Rachamin of his siddur which also includes our non-verse appears in MS JTS 4284, pg. 14. The copying was finished in the year 1605 CE. According to Prof. Ratzhabi, this was probably done in Turkistan. It's important to note that neither Rasag nor Rav Amram Gaon intended for their orders of the Rachamin to be any sort of final version that everyone must follow. Rasag states in his siddur (Mekitzei Nirdamim edition, pg. 264), in the introduction to that section that (my translation):
"And now that most have accepted upon them the custom of saying piyutim of Yom Kippur in the prayer of the Tamid and this doesn't damage the prayer, I will write down for Yom Kippur three piyutim, one for Tamid and one out of two - whatever is chosen - for Mussaf. And then I'll write also 23 selichot, 13 for Tamid and 7 for Mussaf and 3 for Neilah, in short-form, and I'll write long Rachamin, that it is not acceptable to divide them and to say some in Tamid and some in Mussaf, but it is acceptable to divide them in a set order and to say some of them at dawn during every one of these ten days of the month of Tishrei, and to also pick out some of them and to say during every fast that is set on a weekday, and saying more or saying less depends on the wish of the person who says them for he can say as much as he wants."
One last note: Prior to reading @DoubleAA's comment that it would be cool if this came from an apocryphal work, the idea had already occurred to me, along with two other possibilities: a. The Dead Sea Scrolls and b. The Karaites.
I did several searches in the DSS (מאגרים was very useful, they have almost all of the DSS transcriptions) but sadly nothing came up. I didn't search all of the apocryphal works. I focused on works where it would make sense that it might be in, such as Tobit, ben-Sira and the additions to Daniel. Finding the non-verse in apocryphal works still isn't sure-proof because it all comes down to what the original Greek said and how the translator decided to translate it (I once came upon an old Hebrew translation of ben-Sira (I think it was from Greek, but I'm not entirely sure) where it seems that the translator decided to include in the text wise teachings from Chazalic sources he thought were related to the subject matter). Lastly, I started going through some Karaite works. I went through about 3-5 machzorim. Most didn't have any sections of זכור, except for one, סדר התפילה למנהג קהל הקראים, from Venice, 1528:
As can be seen, they didn't include this verse.
