Hmm, if it is in 3D, I don't think it is impossible.
The problem with most of the 3D games is that they lack the speed Sonic is know for, meanwhile a number of Mario's more recent 3D outings have picked up speed and in case of the Galaxy games, included some more physics based gameplay. The issue with combining the two together is that such 3D games don't really lend themselves to having multiple characters unless you are having them switch out on the fly and a 3D world or NSMB game wouldn't let Sonic zip along unless it was online or on the Wii U where each player had their own screen.
I firmly think it is possible... but highly unlikely because it would take too much effort to create. A Kirby crossover with Nights would be more practical to get off the ground then a platforming game with Mario and Sonic. The best bet for a non-sports, non-Smash Bros. crossover with Mario and Sonic would be a RPG style game similar to Mario and Luigi or Paper Mario's first two games.