all' onchange della prima select capisci la regione selezionata e poi:

o metti un grande if (o switch) con le tue possibilità(una per regione)
oppure con ajax mandi la regione allo script che ti invia le città

avendo anche già lo script php pronto la prima è un po' una pazzia, quindi è meglio capire che regione è selezionata, fare una richiesta ajax mandando la regione, farti restituire le città, magari già sotto forma di <option> e inserirle nella seconda select.

Se sai qualcosa di js vedi -> www.html.it/guide/guida-ajax/
altrimenti parti da qui -> www.html.it/guide/guida-javascript-di-base/

se ti servono aiuti per come impostare facci sapere