usa la funzione mkdir().
Serve per creare una cartella, specifica il path assoluto, mi raccomando.

Poi quando usi move_uploaded_file() nel secondo argomento specifichi la cartella che hai creato. =)