Rui's given some good talks about Mold if you want more info: https://www.youtube.com/watch?v=hAt3kCalE0Y
What takes time is rewriting stuff as you go. Running the relocation tables to insert addresses into the code is cheap. Deadstripping sections is fairly cheap, deadstripping individual basic blocks within functions takes a lot more analysis and thus time.
Deduplicating constant strings is a good idea but involves streaming them all into a hashtable of some sort. Maybe you want them to share common suffixes, more work.
Deduplicating, deadstripping, rewriting debug information takes time. Debug builds can feature many gigabytes of dwarf to rewrite.
Oddly enough that the linker is scriptable, as in you can give it a program that it interprets, doesn't seem to be a significant cost. Probably because the script in question is quite short and somewhat limited in functionality.
Historically lld was very fast because it didn't bother doing any of the debug munging or other deduplication. Lld ran fast but the output binary was big.
I'm several years out of the linker performance game now so don't know the current status. In particular I don't know where mold or lld are in terms of quality of output vs their own performance.
https://www.airs.com/blog/archives/38
"Once again, the goal is speed, in this case being faster than my second linker. That linker has been significantly slowed down over the years by adding support for ELF and for shared libraries. This support was patched in rather than being designed in. Future plans for the new linker include support for incremental linking–which is another way of increasing speed."
Just think of the apps that were written in early Unix days - simple single-purpose apps, probably just one source code file , just one obj and libc to link together, no shared libs et al.
The linker code just grew organically as new "must-have" features were added. Correctness of features was more important than speed esp. when spinning rust was a limiting factor.