Your problem here isn't in choosing an appropriate clustering algorithm, its defining an appropriate similarity metric. Edit distance and jaro winkler distance will cover a lot of ground for you, but you should still anticipate needing to do a fair amount of pre-processing and customization here. Also, as great as text-based metrics are, you have much more information here that can be leveraged. Your data is obviously going to have implicit clusters in it already based on documents that are contained in the same folders, and going further those folders exist in a hierarchy which also implies certain groupings. You should make sure that your clustering and/or similarity scoring incorporates these topological features in addition to any text similarity you do.
Your first step is going to be understanding your data more. I'd recommend constructing a tree visualization of the folder hierarchies you're going to be dealing with, taking a sample of 5-10 filenames from within each folder so you can better understand what your dealing with. From here, start trying to understand what kinds of naming conventions are in place that you can take advantage of. There are probably lots of files with dates at the beginning or end, maybe commonly occurring client names, words that are suggestive of document classifications like "report", "newsletter", "resume" etc. The more of these you can capture and deal with directly, the better. Next, you may start seeing some patterns that suggest ways you can further tokenize filenames. spaces, hyphens, and underscores are probably good places to start (after dealing with dates/timestamps, obviously), and CamelCasing would be worth looking out for as well. Also, different filetypes might have different naming conventions. For example, *.png files are probably more likely to have all numeric names starting with dates (i.e. someone dumped their camera to a folder).
If you want to just get really quick and dirty with it, something you could try would be to parse each filename into n-grams (e.g. all sequential 3-letter sequences that occur in a filename) and then score pairwise filename similarity based on the jaccard distance of the n-grams that appear in each filename.
Once you've figured out a couple of different approaches you want to try, you should start thinking about how to evaluate your results. Obviously you're going to start out evaluating things qualitatively, but that doesn't really help you compare the strengths/weaknesses of different approaches. One thing you could try would be to use the naming conventions learned by a particular method to try to predict whether or not randomly sampled filenames appear in the same folder or not, and score your methods based on how well the resulting classifiers perform.
Ultimately, your going to have to custom tailor the solution to what you see in your clients filenames. Hopefully, I gave you a few ideas to work with here.