The desert in question isn't all sandy dunes; there's a lot of rocky or compacted surface (see photo), so you can make pretty decent time (but yeah, sustaining 4mph would be pushing it for most people).
hmm, [0] this says the longest stage was 91km in 2009 (I did it in 2015), so I could be wrong, but I'm going by what my garmin told me.