Говорить мог уже общий предок - гейдельбергский человек. И, скорее всего, по уровню развития речи сапиенсы того времени и неандертальцы с денисовцами не слишком отличались.
Как бы очевидно, что говорили. Одежду делали, копья делали, культура была. Как вы себе таких людей представляете без речи?