If Autoconf requires GNU M4 and GNU M4 has an Autoconf
configure script, how do I bootstrap? It seems like a chicken
and egg problem!
This is a misunderstanding. Although GNU M4 does come with a configure script produced by Autoconf, Autoconf is not required in order to run the script and install GNU M4. Autoconf is only required if you want to change the M4 configure script, which few people have to do (mainly its maintainer).