At first you should have a writeable base directory where PHP would be able to create subfolders. Then in your upload server-side script use an mkdir() command and chmod() to create and set permissions to the directory accordingly, then move the uploaded file to that folder. When you upload the file via your android app, the folder will be automatically created and the file will be moved there.
Here's the code for your particular case:
<?php
$file_path = "uploads/";
$new_name = "new_folder"; // this is the new folder you'll create
$file_path .= $new_name . '/';
mkdir($file_path);
chmod($file_path, 0777);
$file_path = $file_path . basename( $_FILES['uploaded_file']['name']);
if(move_uploaded_file($_FILES['uploaded_file']['tmp_name'], $file_path)) {
echo "success";
} else{
echo "fail";
}
?>
In your question you say you don't know the name of the folder to create. Well, this should be done on PHP side. You should decide on the server what name of the folder to use. In your original code there is nothing that specifies the folder, so it's up to you to decide how you want to do it.