Unlike selicha, which refers specifically to sin, mechila (or mechilah) מחילה has more a more secular meaning as well. The root מחל first appears in Rabbinic Hebrew where it can mean "to remit (a debt)" or "to forgo (one's honor)". It also does carry the sense of "to forgive, to pardon".
Klein states that the etymology is unknown, but Jastrow, Steinberg and others connect it to the root מחה. The complication here is that מחה has many meanings, which may or may not all be connected (for example see Malachim II 21:13, where different meanings of the root play on one another).
The meaning of מחה that most likely led to מחל is "to wipe, wipe out", which also has the sense of "to blot out, destroy". We see this sense in the famous commandment תִּמְחֶה אֶת-זֵכֶר עֲמָלֵק - "wipe out the memory of Amalek".
Another meaning of מחה is "to strike upon". Kutscher points out that this root is related to three other Hebrew and Aramaic roots: מחא , מחק and מחץ . This site summarizes Kutscher's Hebrew article:
There are also genuine Aramaic words which have passed into Hebrew, sometimes in several forms. The Hebrew makhatz (“crush”) is found in the Bible (Judges ), while its ancient Aramaic form is מחק (makhak). In a subsequent period, the same Aramaic root was taken over again into Hebrew in a later form מחא (macho – “to clap hands”), and finally re-entered Mishnaic Hebrew, changing both form and meaning as מחה (machot – “to protest,” actually by clapping the hand). Thus one finds in Israeli Hebrew a single Semitic root in four variations ….
We see that the root מחק also has the meaning "to rub out, erase". The author of the Avinu Malkeinu prayer seemingly noticed the connection between three of these roots:
אבינו מלכנו, מחה והעבר פשעינו וחטאתינו מנגד עיניך
אבינו מלכנו, מחוק ברחמיך הרבים כל שטרי חובותינו
"...forgive and pardon all our iniquities"
"...wipe away and remove our willful sins..."
"...erase through Your abundant compassion"