I think the only way to make this work is to put this in the Makefile
:
all : clean
which you don't want (obviously). My next idea would be:
clean_all: clean
$(MAKE) all
That would allow you to write make -j clean_all
but I'm not happy with it, either.