Yes, they use tilemaps (more precisely : small 8x8 hardware tiles). The main reason is that background scrolling and sprites display on most 16-bit consoles are hardware accelerated (there is a dedicated hardware chip for that, VDP in case of genesis). The only way to use that feature on genesis is to divide the background and sprites into small 8x8 tiles (even for displaying a single full screen logo).
Video memory (VRAM) was very expensive at that time and using small 8x8 tiles allow some tiles to be reused at different locations on the screen. Even if genesis can render games up to 320×480 resolution, there is not enough video memory (64KB) to hold a full frame.
Here is an example for Sonic (same goes for background) :
The background is defined as a 2D array of tile indexes (eg: 0x00, 0x04, 0x01, 0x02, 0x02, 0x03, 0x08, 0x02, ...) and characters (sonic, ennemies, etc) are made using several 8x8 sprites, that stick together by moving on the screen at the same time.
Some consoles allow several layers of tiles (aka planes) to be displayed at the same time (maximum two for genesis). All of them have same size (usually a little bigger than screen) but they be can scrolled independently. This is mostly used for parallax scrolling . These layers can give you the illusion that there is "huge bitmaps" moving on screen while they are actually independent layers of tiles.
Note : most of these games store levels in a different way than just an array of 8x8 tiles. In Sonic game, for example, a level is made using big 128x128 blocks. This allow to store the level efficiently and make level editing a lot easier. In the end these 128x128 blocks are converted in smaller 8x8 tiles (because of hardware limitation).
