The scenario is very compelling. And it certainly would make the III carlist war a lot more balanced.
But i wouldn't place together my idea of federalism with Leopold in the throne, because the reason why the Borbons were restored on Alphonse XII's head was that people were very very tired of experiments. While low on prestige, people remembered the country had been much more stable under the Borbons.
So we basically need 2 things to make it work:
-Reasons for the French legitimists and the Prussians to care about the Carlist war. This would need an earlier PoD, as wolf suggests. Doesn't have to be necesarily something that drastically changes events from there, but something that only triggers at the III Carlist war.
-Reasons for the Carlists and the liberals to accept a divided Spain. Carlists theoretically wouldn't, as much as Charles VII was a "progressive" by carlist standards, because they are traditionalists, their motto is God, Fatherland and King. It would require some kind of strange mixture of federalist regionalism (that already existed) together with the Carlism, a new ideology
*cough*.
Republican Federalists might have an easier time accepting it, but precisely because of this, the republic would surely fall, and Alphonse XII wouldn't be accepting at all.
On the other hand, with Leopold from the get go, he might be happy to get a kingdom at all, but that remove the only window i see for the Carlists to accept a divided Spain (no republic, hence no federalism, unless Carlism and regionalism/nationalism fuse as an offshot of carlism much much faster than it happened IOTL, like 30 years faster).