One approach is to keep a running total of all uploads, (atomically) increasing it for each upload.
Then the directory can be created like so:
$dir = sprintf('/uploads/%d/%d', floor($total / 1000), $total % 1000);
if (!file_exists($dir)) {
mkdir($dir, 0755, true);
}