Criticism of Latin Translation
First, a brief criticism of the Latin text that you are using as a source:
- Expressing purpose: The English of the song is a purpose clause, i.e. "in order to tell you..." Though later Latin can use an infinitive for this, it is more standard to use ut + subjunctive. See my answer to another question about purpose clauses for other options. I did a brief Google search, and it looks like the prevailing Latin translation actually says "ut tibi narrarem."
- Sorry "for" something: Based on my ear and the options in Lewis and Short, I have never seen me paenitet pro + ablative to mean "I am sorry for X." Genitive is far more common.
As a stylistic observation, I would also change "omnium quae feci" (=for everything I have done) to "meorum factorum" (=for my deeds), in the mold of Cicero:
me tamen meorum factorum atque consiliorum numquam, patres conscripti, paenitebit. (Cic. In Catalinam IV 20.4)
My proposed translation:
Tibi ut dicam me paenitere meorum factorum.
So much for a "brief" criticism!
Your English translation
Your translation is spot on except for one thing: aliquem paenitere... does not mean "forgive someone" but rather "cause sorrow to someone." Me paenitet is the standard way of saying "I am sorry" (lit: "it pains me").
This part of the Latin is perfectly good, though I like my proposed translation above better. You are thinking of quis, quis, quid, which is an interrogative pronoun meaning "who, what."
In this case, it is using the very similar qui, quae, quod, which is a relative pronoun, translated to English as "who, which, that." The relative pronoun agrees in gender and number with its "antecedent" (the word it is "standing in" for) and changes its case based on context. For example:
Homo quem vides improbus est.
The man whom you see is bad.
English uses "which" when the antecedent is neuter:
Bellum quod geris iniustum est.
The war which you are waging is unjust.
You can read more about relative clauses here.