How did these people know about the powers of chanting mantras? Specifically how did they know what to say and what exactly they are.
Please see below from Kamika Agama, Purva Pada (Verses 1-3, Chapter 2). Agamas are shrutis (just like vedas) revealed by Lord Shiva himself. So the point of questioning them does not arise.
The first stanza says there is no action is to be conducted without a mantra - be it tilling the land or regular worship.
Second stanza says there "manana" is the ability to know everything, and "trana" is liberation from samsara. Combining these two gives you "mantra"
The third stanza says mantra consists of two parts - vacya and vacaka. Vacya is form of the word, while vacaka is the deep meaning. These two are inseperable.
The Agamas contain details of even the minutest of activity you can think of, and the mantras to be chanted while carrying out those activites.