This shortcut creates a folder and creates a folder with counter appended if an existing folder is encountered. The last action of this shortcut returns the newly-created folder. The base timing result was 70 milliseconds, but approximately 10 milliseconds are added for every existing folder. The following screenshot only shows a portion of the shortcut.
Create Folder.shortcut (23.3 KB)
The following shortcut is functionally the same as the above except that the shell is used. The last two actions of this shortcut return the newly-created folder. The timing result was 130 millisecond and varies little if several existing folders are encountered.
Create Folder with Shell.shortcut (22.8 KB)
I did not write a shortcut with AppleScript solution, because the Run AppleScript action is very slow.