Do atomic operations become slower as more CPUs are added?

For the question posed in the title, the short answer is "yes," the long answer is "it is complicated."

With regards to locks being better, no. Internally a lock has to push at least as much (if not more) traffic over the bus. Think about it this way, if the the processor only has one atomic operation, an atomic compare and swap, you could use it to implement locks and atomic increments. Well at a bus protocol level there are only a few primitives that are used. Locks are not slower than atomic operations because they are doing something different, they are slower because they are doing more of the same thing (from a coherency standpoint). So as atomic operations slow down, locks will tend to slow down comparably.

Having said that, there are lots and lots of papers on the subject and particular cases are complicated. I wouldn't worry about how your code is going to scale on 80 core CPUs that have unpredictable performance characteristics (because we don't know how they will be designed). Either they'll behave like our current CPUs and your code will perform fine, or they won't and whatever you guessed now will turn out to have been wrong. In most cases it will turn out the code wasn't performance sensitive anyway, so it doesn't matter, but if it does then the appropriate thing to do will be to fix it in the future when when you understand the architectural and performance characteristics of your target processors.