Yes. This is a constant issue when non-scientists discuss scientific theories. A law is just a convenient equation that works sometimes, in certain conditions.
Except this is closer to a mathematical theorem than a law like say, boyle's law. You might be able to re-write an algorithm so it has a larger portion that's parallelizable, but that's the only way to get around it. You can't just keep adding parallel computers and enter a qualitatively different regime.
It's a model that tells how something will behave under certain conditions. It works if the program being run can be neatly separated into purely serial and purely parallel (infinitely scalable) parts. In reality it breaks down at some point because nothing scales forever and there is some communication overhead.
It is similar to the ideal gas law, for example, which can be proved from the axioms of classical thermodynamics and yet fails when the molecules start interacting.
Laws span the whole spectrum from purely empirical to provable within some theories' frameworks.
