Disclaimer: I was mechadeish this p'shat based on the sources mentioned below. If you can find this p'shat somewhere, that would be amazing, but I have not seen this explanation anywhere. If you don't like it, feel free to disagree.
The Ramban (to Devarim 4:2) says, and I'm paraphrasing here, that the issue of Bal Tosif is that you can't add a Mitzvah and claim that it was commanded by Hashem. Making up a Mitzvah and saying that it's your own thing is not problematic in the least, assuming that it doesn't contradict something in the Torah. (Side point: After all, isn't that what a minhag is?)
Bal Tasur, on the other hand, authorizes the Rabbanan to make up their own things that they can then impose on all of us. Obviously, though, this has to fulfill Bal Tosif: they can't claim that Hashem gave new Mitzvos after the 613 were completed, nor can they make new Mitzvos that contradict the Torah.
Now, there's one other thing I'd like to point out before I put forth my chiddush. Just about everywhere in the Torah where it says "Tzav" Onklos translates it as "appoint," not "command." Appointed to what? According to a shiur I heard from Rabbi Yochanan Zweig on Parshas Tetzaveh (note the same root) it's a reference to the pesukim of "v'hayu li mamleches kohanim v'goi kadosh" and "u'vecha bachar Hashem lihiyos lo l'am segulah mikol ha'amim." Thus, a more literal translation of the Brachah would be "Who sanctified us through His appointings and appointed us through our doing the Mitzvah of ____."
Thus, when we're making the Brachah on a D'Rabbanan, we're not saying at all that Hashem commanded us to do the d'Rabbanan. We're saying that Hashem is appointing us as His treasured nation, and in return, we fulfill His mitzvos. Thanks to Bal Tasur, that includes mitzvos such as Menorah. Thus, to use that Mitzvah as an example, the Brachah would be "Who appointed us through the Mitzvah of Menorah." We don't say anything about Hashem commanding us to light the Menorah for eight days every winter. However, the Gemara that says it's because of Bal Tasur (quoted by @Ephraim) is still correct; since it's a Mitzvah D'Rabbanan, as authorized by Bal Tasur, we get s'char for fulfilling it, and we can use it to draw closer to Hashem as a member of His am segulah.
We could apply the same logic to Hallel on Rosh Chodesh. Although it's only a minhag, we (at least Ashkenazim) say the Brachah. Nevertheless, we're still drawing closer to Hashem by praising Him, and thus we can make the Brachah.
This all fits in very nicely with the Maharal @Y ez brought up, that the Mitzvos d'Rabbanan are to help a person do what he should be doing anyway. Thus, we make the Brachos because, again, the Mitzvos help us draw closer to Hashem.
As for Pruzbol, that's literally just a loophole to avoid having to let go of debts after Shemittah. Since it's not a mitzvah whatsoever, we wouldn't make a Brachah about being appointed through doing it.
Now, I'm sure you're wondering: what about Purim? The Gemara (Megillah 14a, Yerushalmi Megillah 6a) made a whole big deal over the fact that Purim isn't in the Torah. The difference, though, is that the Gemara is discussing a violation of Bal Tosif. Once we've confirmed that Purim (and according to the Ritva, as quoted in that last link, Chanukah, too) is a perfectly valid Mitzvah, we can then make a Brachah on it regarding drawing close to Hashem. Chazal seemingly wanted, for whatever reason, to make Chanukah and Purim on par with chagim d'Oraisa, and thus they needed a proof from the Torah that these chagim were able to be such.