This Gemara is dealt with by Rav Elchonon Wasserman in קובץ מאמרים - מאמר על תשובה who helps to give us a bit more of an idea as to the functioning of this regret.
As with all good answers - one needs to ask another question by way of introduction....
Rav Elchonon bases his question off Mesillas Yesharim chapt. 4 that points to the fact that if Hashem only had Middas HaDin (the attribute of judgement), we would stand no chance as strict punishment would be meted out accordingly. It is only due to the fact that He also has gifted us with Middas HaRachamim (the attribute of mercy) that we have the ability to correct our past misdeeds, and through Teshuva (repentance) we can erase previous sins in their entirety.
Yet the above cited Gemara demonstrates that regret uproots all of one's mitzvos and therefore how can the Ramchal say that the power of teshuva stems from middas harachamim? It would seem that the notion of 'regret' is strong enough on its own merit - i.e. in the same way regret can erase the bad, it can also erase the good? The implication from mesillas yesharim is that Hashem alone has the capacity to erase sin whereas our Gemara says that the power lies with regretting the action.
He brings two answers from his Rebbi the Chofetz Chaim that; 1 - teshuva mei'yirah (repentance borne out of fear) spurs a person on to repent out of fear of the possible punishment and not through regret. 2 - Conversely if the repentance was borne out of love (teshuva mei'ahava) it helps to reformat the act into a mitzvah, but doesn't erase the sin.
So it would seem that regret is a different element in its own merit. At this point I started hunting around on the internet to see if anyone builds off Rav Wasserman's point and I found an amazing article here.
Also, I wonder, what kind of Toheh is the Gemara in Kiddushin talking about? Is it talking about a Toheh that matches the Teshuva we are told to do? Is a man called a Toheh only if he deliberately and thoughtfully reexamines the mitzvos he did, is deeply ashamed of them, mournfully regrets doing them, and makes a firm conscious decision to never do mitzvos again? Does he have to re-create himself, as the Rambam says of the Baal Teshuva? I doubt it. It means just what it says: that he regrets having done the mitzvos. If that's enough to erase mitzvos, why wouldn't similar regret be enough to completely erase aveiros? Why does teshuva require the wrenching effort of בְּכָל לְבָבְךָ וּבְכָל נַפְשֶׁךָ?
Unfortunately, this all seems to point toward something I've often quoted from a well known and highly respected Mashgiach that I've had business with.
"Good Comes and Goes, but Bad is Forever."
He didn't put it in those exact words, but pretty close, and I think the aphorism sums up his philosophy, that a spiritual fall generates an indelible change that forever increases the risk of relapse. Spiritual advances, on the other hand, are fragile, easily lost, and effortlessly extirpated. They disappear easily, and when they do, they don't leave a trace.
Reb Yitzchak Hutner in his Pachad Yitzchok answered Reb Elchonon's question along the same lines (minus the cynicism.) He said that going from life to death is part of the teva, the natural order of Hashem's universe. Going from death to life is not. Order requires constant energy, while disorder is the default state. Anyone can be meimis a chai. Not everyone can be mechayeh a meis.
In short, our bad middos take root quicker and are harder to uproot than our good middos. As such, 'toheh' - regret is a more natural, in borne reaction and so would seemingly take effect quicker, whilst the notion of teshuva is something that supersedes the natural world and requires Hashem's input. So regret by mitzvos is effectively a person naturally coming to the conclusion that he harbours remorse at the good actions he completed in his lifetime and is willing to forgo their fulfilment. Alternatively, the desire to do Hashem's will is what drives our mitzvah fulfilment - thus if you do the mitzvah without intending for it to be a mitzvah, you haven't done anything. Whereas, an aveira when done fleetingly, is still considered an aveira. So when the person in the gemara regrets his mitzvos, he is for want of a better word, completely disregarding their performance and therefore it is like he never did them.