As SpartaLazor says, that first idea explodes very quickly because there's lots of combinations between Pokémon. Even if you restrict your region to only a hundred Pokémon you're still talking about thousands of combinations, and it's not just sprites, you also need to think about naming, stats, typing, move pools and abilities!
So I think you're basically required to go down the same route as Infinite Fusion and come up with an algorithm that can combine two Pokémon and produce all the above. That said, it's obviously possible, and I think you could probably improve on Infinite Fusion's approach if you had some artists at your disposal. I imagine you could also tweak that algorithm to have different types for existing Pokémon (i.e. Delta Species), or even procedurally generated Fakémon!
IMO the challenge is to produce a better generative art algorithm. I've done some limited research work in that area — writing algorithms to produce 3D models of buildings based on the kind of architecture — so I have some opinions and ideas but am definitely not an expert, so take my suggestions with a large pinch of salt:
I think you break each Pokémon's art up into what kind of body it has, what components are on that body and its colors. For example Scyther is bipedal, green and yellow, and has a torso, head, arms, legs and wings; Mareep is on all fours, blue and yellow, and has a torso, head, legs and a tail; Goldeen is a fish, white and orange, and has a body, a horn, fins and a tail.
I would want to avoid allowing fusions between different "kinds" of Pokémon, but the obvious restriction is by egg groups and you'd still have some weirdness to fix there (e.g. in
Water 1 we have Squirtle, Slowpoke, Horsea and Omanyte just from Gen I) so you'd probably have to come up with a rule on how to merge the different kinds by picking which parent to inherit it from (or if you're feeling ambitious you could take it from the male parent, à la
ligers and
tigons).
To merge two Pokémon you just choose which components you want to inherit from each parent and what color scheme to use (which is probably based on the fused typing), and them combine those components.
The trick is coming up with a way to make it easy to merge arbitrary components, for which I have two ideas, the second of which is quite experimental:
1. Sprite all the components for each Pokémon in a generic palette and the same perspective and sizes which you can overlay in the correct positions. You'd need to identify where to do the joins (e.g. where the shoulders are for each torso) and if you're supporting merging different kinds of body you'd need a different sprite for each kind (e.g. a Jynx-Goldeen fusion might take Goldeen's fins as a skirt).
2. Write code that generates a particular component given the color scheme and size of the body part it's attached to (so that you're able to have reasonable proportions). Call all the functions for those components and overlay all the returned sprite-parts.
If you wanted to go beyond fusion into Deltas and the like I think you could include the type in how you describe the components. For example Electric types are often spiky like Zapdos or Manectric, and Fire types often have flames like Ponyta or Litwick. To my mind this seems like it would be much easier with option 2, because it turns an N×M problem (N Pokémon's components × M types) into an N+M one (N component-functions + M ways to generically modify those functions to suit types).
Aaanyway I have a feeling that this reply is way more detailed than you expected or even wanted, but this is an idea that I've always wanted to write up and pitch. If any artists out there wanted to give this a go I'm available to write the code, heck if there's another developer out there I could even try to draw (but fair warning, it'd be
Tom Bus level at best).
