Before getting to an answer, I want to make some observations about the question. Firstly, I think modern readers might be troubled by Moshe's second question even without the background of the first. What do you mean, "In what merit do they deserve redemption?" Didn't Moshe ever hear of Thomas Jefferson, of inalienable rights? It would seem that the ba'alei Medrash may not have shared our political theories. Secondly, I wonder what troubled Moshe when he asked that first question. Was it simply the degree of suffering, i.e. there was some quantitative threshold which he perceived had been broken through, or was there [and is there] some qualitative difference to Jewish suffering that places it on a different plane? [I would suggest that it is the unconscious assumption of the latter position that causes such grief when the term 'holocaust' is used to describe tragedies other than that of our own.] Finally, cynic that I am, I wonder if Moshe's change in perspective is the result simply of maturity. Moshe the young man, perhaps still in the hold of idealistic notions of life, struggled to reconcile suffering and tragedy with his world view. Moshe the more worldly and wise has grown to accept suffering as the norm of life and it is freedom and happiness which he takes to be the exceptions that warrant explanation.
Rather than give the Shem m'Shmuel's answer (which you can look up), I want to suggest an approach based on a Maharal we discussed once before (and which the Shem m'Shmuel coincidentally cites in quite a few places). The gemara (Kesubos 66) tells us that Rabban Yochanan ben Zakai came across the daughter of Nakdimon ben Gurion picking through animal dung looking for food after the churban. Recalling the tremendous dowry that was pledged in her kesubah and now seeing her so degraded, R' Yochanan exclaimed, “Ashrecha Yisrael! – When the Jewish people do G-d’s will, there is no one who can surpass them, but when they fall, they fall to the lowest depths of animal dung.” It’s understandable why R’ Yochanan ben Zakai would say, “Ashrecha Yisrael!” on the ability of Klal Yisrael to rise to the greatest heights, but the, “Ashrecha Yisrael!” seems to refer also their being in the lowest depths as well. How does that make sense?
Maharal explains that the fact that when we fall, we fall good and hard to the lowest depths, proves that our fall is not just some turn of history, just another accident of fate – the overwhelming force of our destruction can only be attributed to hashgacha. Therefore, we can be confident that the same guiding force that drags us down when reversed can carry us to the greatest heights. The neshoma of Klal Yisrael knows no passive middle ground -- it either unleashes a powerful thrust of positive energy, or leaves a gaping chasm that inevitably becomes filled with negative poison.
"Achain noda ha'davar" meant Moshe came to understand this idea of Jewish exceptionalism. If the reason why Bnei Yisrael suffers is because yad Hashem, hashgacha pratis, determines their fate, and therefore their downfall is so steep, then their freedom also must come not from some theory of inalienable rights, but rather must stem from that same well of hashgacha.
This is why Moshe asks Hashem, "In what merit have Bnei Yisrael earned a miracle being done for them to redeem them?" Who said anything about miracles? Hashem had just told Moshe that he would take Bnei Yisrael out of Mitzrayim -- he never said how, nor did me mention anything about the supernatural. Yet, Moshe understood that a redemption that comes b'hashgacha pratis is one which by definition deviates from the natural order.
One final point: The Sefas Emes also asks this same question aand gives his own short but striking answer. It was because Moshe came to understand that it is the cheit of lashon ha'ra in particular that was the root cause of Bnei Yisrael's suffering that he questioned whether they had any zechuyos that would warrant their being redeemed. So great is the evil of lashon ha'ra that Moshe thought it inconceivable that anything could overcome it.