What is more precisely true is that the time taken by dirty checking per second scales with d×w×l, where d is the number of digest loops triggered per second, w is the number of watches, and l is the length of the digest cycle (the number of times that the watches are rerun before values stop changing).
Specific applications may find these variables to increase in different ways - all three will generally increase with application size, but for example, adding a digest on mousemove will immediately send d to a very high value.
What I really meant when I said O(N^2) was nothing precise though - just that, when I first read "every time you trigger a digest, we traverse every watch," it sounded like N^2 - it fit the pattern of "for every one of (growing number of things), do each one of (growing number of things)".
Digest on mousemove wouldn't be a good idea - look at _.throttle etc. You shouldn't realistically need digest loops more than once per 100ms, as people can't perceive changes happening faster.
I agree with a lot of what you say, but wonder if you're being rhetorical when you say Angular's popularity is baffling. Do you actually think that people pick tools by reviewing the CS literature and picking the one that best reflects the state of the art? :)
Angular is productive, people want to get things done; thus Angular is popular.