This is the leap I believe is incorrect. The paper doesn't explain how CNAME cloaking helps evil.com track users across sites. It says that it does, but it doesn't actually explain the attack vector.
It is far more plausible to me that CNAME tricks are being added so that evil.com can track a user on an individual site. When uBlock Origin is putting a hard block on all traffic to evil.com, there's still quite a bit to be gained by shifting evil.com to evil.foo.com if that means requests start succeeding again.
Another poster said something similar here: https://news.ycombinator.com/item?id=26349987
Then, when evil.com receives a different auth token for the same user visiting other.net, how does evil.com know that new auth token correlates to the same user on example.org?
This is the third-party identity linking that's now impossible for evil.com to accomplish independently. They need other.net and example.org to share some common information (like an email address) to make the link. For logged out users, it should be impossible without resorting to fingerprinting.
This was Firefox and Safari's entire reason d'etre for launching Total Cookie Protection and Intelligent Tracking Protection. I don't believe CNAME cloaking overcomes their protections, or at the very least, I don't see where this paper explains an attack vector.
The bottom line is that evil.com would not be asking sites to install CNAME tricks in their domains if evil.com cannot leverage those tricks to track users across sites. That should be obvious.