Is there a way that users can create New Folders that will then be added to the multiple select list for other users to sort their uploads into? 

No it can't be done with the profile fields.