Document clustering to merge common labels
I might misunderstand something but it looks to me like you're trying to find a complex method for a simple problem: if there are many strings which occur multiple times in the list, you should deduplicate the list before comparing all the pairs. You could use a set, but since you will need to count how frequent each string is you should probably directly create a map (dictionary) which stores the frequency for every string (just iterate over the list of strings, then increment the frequency of this string (key) in the map).
Depending how many distinct strings you have, this simple step might be enough to allow you to compare all the pairs of strings efficiently.
Then you could for example decide on a threshold for frequency, for instance keep only the strings which appear at least 10 times. For any string which appear less than 10 times, replace with the frequent string (more than 10 times) which has the highest similarity with it.