I have run Lintian against a (Ubuntu) kernel package. It took 1702 seconds, (~ 28 min). Of that time, the profiler analysed 1225 seconds (~ 20 min) I profiled it using the NYTProf Perl profiler. Here are the results:

We can see that most of the time is spent in the visit_files function. The plugins that take the most time are:
- Files::Contents::LineLength with 237s (~ 4 min)
- Files::SourceMissing with 225s (~ 4 min)
- Languages::Python::DistUtils with 143s (~ 2 min)
- Cruft with 81s (~ 1 min)
So, if we would be rewritting some parts of Lintian in (parallel) Rust, the best candidate would be these plugins.
The idea would be to rewrite these checks in Rust, make the lintian-ng program call the Rust checker, and then a fork of the Perl code that has some plugins removed from it. This would allow for an incremental rewrite. Everytime someone rewrites a check in Rust, we can remove it from the Perl codebase.
It if funny to see that the DistUtils check takes 2 minutes for a package that is not supposed to hold much Python code.
Commands used:
$ perl -d:NYTProf ~/dev/debian/tmp/lintian-2.117.0ubuntu1.1/bin/lintian
$ nytprofhtml --open