The default hash functions in most C++ implementations are surprisingly slow—implementations tend to aim for hash quality rather than speed.
I can be totally wrong, but I suggest trying a simpler hash such as FNV. It might outperform the sort-based approach.
I also suggest replacing the hash table implementation with something better, such as absl::flat_hash_map. The C++ std::unordered_map is hampered by compatibility requirements: the designers wanted these unordered containers to be a good substitute for the preexisting std::map, and necessitated certains design decisions such as pointer stability which is not necessary for most applications.
A slow hash-function doesn't explain the increasing time-per-element as the hash table grows though. A poor fit between the keys and hash-function might though.
I can be totally wrong, but I suggest trying a simpler hash such as FNV. It might outperform the sort-based approach.
I also suggest replacing the hash table implementation with something better, such as absl::flat_hash_map. The C++ std::unordered_map is hampered by compatibility requirements: the designers wanted these unordered containers to be a good substitute for the preexisting std::map, and necessitated certains design decisions such as pointer stability which is not necessary for most applications.