I recently had to go the delete and recreate route to shrink the size of an NFS directory after it had previously bloated. In the process, I found a fairly efficient way to do this using rsync and hard links that avoids copying the actual files, while still accomplishing the goal of recreating the directory with the same contents.
You can change the first move command to an 'rm -rf' on the source directory, which is simpler, but the move is faster. Speed from start to finish here was important for us, since we needed to take downtime to do this operation during our maintenance window.
I extracted these commands from a larger process, and abstracted the directory names, so apologies if I've made a mistake in that translation.
rsync -ai --delete --link-dest=/path/to/source_dir/ /path/to/source_dir/ /tmp/holding_dir/
mv /path/to/source_dir/ /tmp/deleteme/
mv /tmp/holding_dir/ /path/to/source_dir/
Then later, we remove the directory. Depending on size, you may need to use a more sophisticated technique to do this, for example using rsync to sync an empty directory into this directory, effectively deleting everything.
rm -rf /tmp/deleteme/