It's a kind of action platformer, a bit like the LEGO games or the Nicktoons Unite series, but with more polish. Basically, Sonic and Eggman are fighting as normal and then a machine of Eggmans (yours, hopefully), explodes, opening a rift into the Mushroom Kingdom. They fall through and Sonic lands in Bowser's Castle. He sympathizes with the Koopa Cause because he's all about stopping greedy humans from beating up animals, and Bowser lies. The same thing happens in reverse when Eggman lands in Peach's Castle, as Mario is used to fighting out of control non-humans with violent tendencies. They adventure and fight each other through the kingdom as the portal in the sky merges in more and more Sonic elements, and eventually Bowser and Eggman meet. Eggman thinks he can control it and remake both worlds in their favor, and it is around this time that Mario and Sonic reluctantly begin working together to save their worlds. Though they still don't like each other much. And after the climactic final boss fight, they loose. The villains loose control of the rift and it fully merges both worlds.
Then we get a handful of spinoffs. We get Tails and Luigi's Mansion. We get Knuckles in Donkey Kong Country. We get Wario and Shadow Land. We get a platforming game with Mario and Sonic, using the 2D and 3D platforming styles for each character like Sonic Generations (Boost Sonic and 3D World Mario). We also get Mario and Sonic Kart and Mario and Sonic Party. All the characters in each of these titles talk and act like the worlds have always been merged together and they always knew each other. And we get to see them palling around and fighting villains together. But something is always nagging at them that something is wrong. They can't tell what though.
Finally, we get a sequel to the original game. The dimensions begin falling apart, restoring the memories of Bowser and Eggman, who attempt to carefully separate the two worlds carefully so all of existence doesn't destroy itself. Sonic and Mario don't know that though. They just think that they are trying to cut the world in half to make it easier to conquer. Eventually the memories are restored, Sonic and Mario have a greater appreciation for each other, and all of the heroes and villains work together to stop the rift. After a climactic final boss fight against Chaos fused with Bowser's Galaxy Generator, Eggman and E. Gadd finish the reverse TOASTIE and pull the worlds apart. Sonic and Mario say their goodbyes, agreeing that neither is really as bad as the other thought at first, and then they leave. Then we get a live action bonus scene with Shigeru Miyamoto and Yuji Naka talking to each other about the nature of video games and creating a world.