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) :
This main character is made using several 8x8 sprites, that stick together by moving on the screen at the same time. Same for background which is a 2D array of tiles.
Some consoles allow several layers of tiles (aka planes) to be displayed at the same time (maximum two for genesis). They usually have the same size (a little bigger than the screen) but can be 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.
