In the sugya of mitzvos tzrichos kavana 115a, which speaks about a case where one is using marror for both karpas and marror, there is a machlokes Rav Huna and Rav Chisda whether you make the bracha of על אכילת מרור by the eating of marror, or earlier by the eating of karpas. Tosafos explains that both Rav Huna and Rav Chisda agree to Reish Lakish 114b that mitzvos require kavana and he will not be yotzei the mitzvah of marror with the eating of marror by karpas. Yet, Rav Chisda holds לאחר שמילא כריסו הימנו חוזר ומברך עליה!, it doesn't make sense to eat marror without a bracha of על אכילת מרור and only make the bracha later. Therefore, he should make the bracha earlier by the eating of karpas. Tosafos questions how one is able to make a birchas hamitzvah on the eating of karpas if he isn't going to be yotzei the mitzvah of marror until later. Tosafos writes that the bracha made earlier works since he is going to be eating a little marror at the time of the bracha, even though he isn't going to be yotzei until later. Tosafos even implies that he doesn't need to eat a kezayis at the time of the bracha, so long as he eats a kezayis later on. It seems from Tosafos that one can make a bracha on a ma'aseh mitzvah, even though the kiyum hamitzvah will not be until later.
Perhaps this approach can be supported from the mitzvah of sefiras ha'omer, according to those who hold that there are 49 components to be yotzei the one big mitzvah of sefira. We make a bracha each night on the ma'aseh hamitzvah even though the kiyum is pending until the last night. However, by sefiras ha'omer each night one is at least doing a component of the mitzvah that will ultimately make up the greater mitzvah of sefira. But in the case of Tosafos, the marror that is being eaten as karpas on which he is making the bracha ultimately contributes nothing to the fulfillment of the mitzvah.
Tosafos draws a parallel from shofar where we make a bracha on the tekios d'meyushav, even though the mitzvah d'oraysa is only fulfilled by the teki'os d'me'umad. The Chazon Ish (O.C. 124) points out that this is also a difficult comparison because by shofar there is at least a mitzvah d'rabonon being done with the teki'os d'me'yushav so that it is not a bracha l'vatala, but by marror there is no mitzvah at all being done with the marror of karpas. What is the comparison? It seems that Tosafos is not focused on the bracha being l'vatala. They take for granted (even though it seems difficult) that since he is doing the ma'aseh mitzvah it wouldn't constitute a bracha l'vatala. The concern of Tosafos is how does the bracha done earlier work for the mitzvah performed later, which they prove from shofar that just like the brachos on tekios d'me'yushav works for the later te'kios d'meumad, so too the bracha on karpas works for the eating of marror later.
There is a machlokes Rashbam 119b and Tosafos 120a whether the primary mitzvah of matzah is fulfilled with the first eating of matzah on which we make a bracha or on the matzah of afikomen. Rashbam understands that it is the matzah of afikomen and therefore draws a parallel from Rav Chisda that a bracha could be made on the ma'aseh mitzvah that is done earlier, and work for the kiyum hamitzvah that will only be later. Tosafos agrees that according to the Rashbam it would be a good comparison, but holds that the primary mitzvah of matzah is fulfilled with the matzah eating l'tei'avon at the beginning of the meal.