Proof is tough, but there are approaches to reasoning about it. One is statistical models of phoneme development which indicates that languages in Africa started diversifying up to about 150,000 years ago.

However I think it seems likely that our cognitive ability to reason about linguistic structures is an adaptation of our ability to reason about making and using tools. Tools leave physical evidence, so if we can figure out an evolutionary relationship with language development we might make traction that way.

With difficulty, but that's not really relevant to the issue here is it? Nobody is arguing that early humans couldn't have communicated.