It turns out to be a case of just RTFM. You can create playlists for MPlayer from directory listings, and then associate playlists with a particular mplayer command.
To generate the playlist from all files in a directory, I use the following:
dir * | sed 's/\\//g' > all_videos.pls
The sed part of this command removes the \ from escaped spaces... i.e. a file 'Hello world' is output from the dir command as 'Hello\ world' - the space is escaped. We need to generate a file without these escaped spaces for it to work properly.
I use the following mplayer command associated with the pls extension:
mplayer -shuffle -fs -zoom -quiet -vo xv -playlist %s