After some researching via performance profiling, we found that 55% of the time is spent in the List<T>.Sort call tree. A lot of that is where the comparer is calling into the shell to get the property values. Since the default List<T> sort algorithm calls to get a value several times for each object, and each one of the related shell API calls takes some time, we could possibly improve that with some caching of the property values, at least for that particular overall Sort call session.
Another 42% of the time was spent in logic that reorders the ObservableCollection<T> after the list sort is complete, so that the order of the main ObservableCollection<T> matches the final sorted list results. This involves a lot of calls to ObservableCollection.MoveItem. Each one of those calls raises an event that is handled by the control so it can reposition any visible TreeListViewItems and ensure that the selection is maintained. We can look into this some more to see if anything can be improved here, but I'm not sure. Doing a "reset" collection change notification instead would be fast, but would lose the selection.
We worked to add property value caching as described above and obtained a 700% increase in sorting speed when testing in C:\Windows\System32. It went from over 5 seconds to under a second. We also tried some other optimizations within the ObservableCollection<T> update logic and slightly improved speed a bit further there too.
The updates will be in the next maintenance release.