No. PROGMEM is not slow but it kind of defeats the purpose of dynamic allocation.
With progmem it becomes ROM tiled or what is in everyday called a char-rom 
My VideoBlaster platform runs with ROMtiles or text chars.
Your are in charge of your own program so if it doesn't require all 128 tiles then just lower the amount.
Change the size of DHGmem and lower the test for maxtiles in the Dpset function and it should work.
The thing with sprites (like the DHG takes care of) is that, say an 8x8 sprite, takes a single tile when at a position multiple of 8.
Once its moved a single pixel to the left or down it takes 2 or 4 tiles because of the boundary.
There isn't much time in the pixelshifting for or-ing pixels so the data really needs to be prepared on a linebasis.
And then there isn't time to prepare the next line.
For your space invaders example, you poke out a number of fixed tilespointers in videomem.
Then you animate them by changing data directly in the DHGmem.