Looking around, it seems it was pretty common to have sprites that weren't 8x8... in the Pokemon screenshot above, the Pikachu and the Eevee are probably bigger than even 16x16. If bending the rules was acceptable then, why bother with having a grid now?
Because if they broke them, it would no longer work on the gameboy.
The answer is that they didn't break them. They most likely used several 8x8 or 8x16 sprites together (8x16 sprite mode involves using two tiles to form your sprites and is a hardware feature).
You'll probably never see an actual sprite wider than 80 pixels on an actual GB, and if you do somehow see one of that width, either they're actually putting it onto the scrollable "background", or they have left absolutely no breathing room to handle sprites on either side, OR they're flickering through the sprite objects.