Simple methods are perfectly fine -- yes, maybe a quad-tree or some such is the optimal algorithm, but its also a rather generalized one; oftentimes a simpler solution will do when it fits your own needs better, and sometimes its just as fast--or faster--than the optimal general solution. What Sonic did is a neat trick for exactly that kind of game, its an excellent example of looking at your needs and constraints, and coming up with a solution that does what it needs and no more.

That said, nothing on the genesis or contemporary systems would have approached "large numbers" of enemies by computational-complexity standards. In 3D space, or with a great number of objects to consider (especially if you have to test whether they interact, as in an n-bodies simulation) you probably do need a way to easily partition the objects that might interact. In 2D, with relatively few objects to consider, its often sufficient to simply check whether an object is potentially on-screen before blitting it, or within a slightly larger rectangle to "activate" autonomous entities ahead of time, just so that it doesn't seem like life suddenly springs into being right at the screen's edge.

In a 2D overhead RPG I wrote in my early days, that's exactly what I did -- NPCs activated half-a-screen outside the visible area in every direction, so even if the player stood still, nearby NPCs would come on-screen, leave, and come back at will. If they wandered too far they'd suspend and remain near where the player would have expected them to be. This all lent to a more immersive kind of feel, without spending resources to calculate all the NPCs in the entire town.

A grid is a tried and true very simple method. Whatever sized your world is, split it into evenly spaced grid cells and then based on where the viewer is in the world, it's super trivial to calculate the min and max bounding extents of the grid to isolate the small subset of objects that are relevant to where the camera is looking.