The VIC ii chip provides hardware support for 8 pixels of scroll in the horizontal and vertical directions. To scroll more than 8 pixels the program needs* to modify the screen data and the color ram. The screen data can use a double-buffering approach but color ram must be updated on the fly, using the vblank interval and/or racing the raster beam to update the lower part of the screen memory before it is displayed.
The fastest possible screen update code on a stock C64 is a completely unrolled loop of LDA/STA : load a character value into a register and store that value to the screen ram. That takes 8 clock cycles (fully unrolled) or 9+ clock cycles (partly unrolled). To update 1k addresses of screen data + 1k addresses of color ram takes a theoretical minimum of 16k cycles of processor time, fully unrolled wasting 12k of code space. More realistically for a game this would be partial unrolling and take somewhere over 19k cycles.
A PAL display (Europe) updates at 50 frames per second; a NTSC display (US version) updates at 60 frames per second. In the PAL version that is a maximum 19656 cycles per frame if the display were disabled; with the display enabled and sprites in use the VIC ii "steals" some of the cycles from the processor leaving under 18.5k cycles remaining.
This makes it impossible for a full-framerate game with no additional hardware to do scrolling as fast as this Sonic appears to do. There just are not enough cycles per frame to process the video memory moves, much less carry out any game logic on top.
The Ram Expansion Unit (REU) gives two advantages: one is just to enlarge the storage space of how much memory can be quickly accessed on top of the machine's built-in 64k. This allows larger maps and more game logic to be stored. But the REU has one more feature that is important here: Direct Memory Access (DMA). The REU has the ability to do the same thing the Vic ii chip does: it can "steal" cycles from the processor and use them for memory access. The Vic ii chip only steals cycles to read memory (for screen and sprite display) but the REU can steal cycles to write memory.
The REU's DMA can write sequential memory like in the screen display or color ram at a rate of 1 byte (or color nibble) per cycle. So in contrast to the processor, which requires over 19k cycles to update the whole display memory, the REU can do it in 2k cycles.
But in its era, the REU was an expensive and not widely-owned bit of hardware. No commercial games used this approach for accelerated scrolling.
*there is a hardware trick to cause the VIC ii chip to display a mis-aligned version of the screen data, which allows scrolling by more than 8 pixels with only a fraction of the data updates required. Unfortunately this trick (named Variable Screen Position (VSP) by the demoscene community) causes the VIC ii chip to send out-of-specification signals to the system ram, resulting in memory corruption on a significant percentage of C64's. Thus this approach was also not much used in commercial games releases. [1]