There are probably a bunch of weird limitations on the adjacent colours you can achieve, but it’s an impressive effect regardless!
(Here’s the obligatory wikipedia page: https://en.wikipedia.org/wiki/Composite_artifact_colors It sounds like the demo developers have taken this effect & turned it up to 11.)
"QPs 512 mode is pretty straightforward; its only color limitation being that it can display a maximum of 40 colors on a single scan line. Mode 4K uses a special technique called "interlacing" in order to display a supposed 4,096 "colors -- http://www.atarimagazines.com/startv3n2/quantumpaint.html see also http://www.atari-wiki.com/index.php/ST_Picture_Formats
Opening the left and right borders however required doing it for each line, I recall, which uses a lot more CPU time. (Unless, of course, there's a trick I don't know!)
Spectrum 512 uses NOP timings to swap the palette at regular intervals throughout the screen; the "4096 colour interlaced" mode just flickered between one colour and another on alternate blanks to give the visual impression of flickery intermediates (before the STe came out, which used the high bit of each nybble to actually have 4-bit-per-channel palettes of 16). That technique, in turn, came from the C64 scene, as did the border trick, though I think they wrote the screen address?
What's old is new again: plenty of lower-end TN LCD panels pull the same colour trickery to fake 8-bit colour from 6-/7- bit panels (or, reportedly, 10-bit deep colour from 8-bit ones in some cases).
This demo is crazy. I don't think CGA even gives them a VBL to hang off! Wonderful.
On the C64, you could pull the border in the width / height of one character in order to support smooth scrolling (coupled with registers to set a 0-7 pixel start offset for the character matrix). This was done so that the borders wouldn't move in/out while scrolling.
By turning this option on/off precisely timed, the VIC graphics chip never found itself at the "correct" location to enable the borders, and so never did.
Opening the top/bottom borders was done very early because it didn't require much timing.
Opening the left/right borders with static sprites happened soon afterwards.
Opening the left/right borders with moving sprites was particularly nasty because the VIC "stole" extra bus cycles from the CPU for each sprite present on a given scan line, so if you wanted to move sprites in the Y position and open the borders, you needed to adjust your timing by the correct number of cycles for each scan line, often done by jumping into a sequence of NOP's. There were additional complications, but that's the basics.
I think DYSP (Different Y Sprite Positions) on C64 was first achieved in 1988.
That's known as temporal dithering/FRC (http://en.wikipedia.org/wiki/Frame_Rate_Control ). To get the 2 more bits of "fake" colour depth requires a 4-frame cycle, on which you display either the darker or lighter colour in sequences like 0000, 1100, 1110, and 1111. It's a form of PWM and the same technique used to drive those large outdoor graphic LED display signs, although to avoid flickering the frequencies are in the tens of kHz.
You could also change those 16 colors for every scanline (horizontal line).
Overall there was a lot of control, but software such as Deluxe Paint did not support full possibilities of HAM mode.
Oh and, btw, EHB (extra halfbrite) mode has 64 colors. 32 colors palette + second 32 colors with brightness halved. http://en.wikipedia.org/wiki/Amiga_Halfbrite_mode
[0] Example: https://www.youtube.com/watch?v=TfVe9l77zLU
I wonder how much you could improve the effect (i.e. the woman after the 4:00 minute mark) by making it move. From the way it's drawn I'm not sure if you could get even 2 fps though.