How much of that is just literary flourish.

Herodotus was an early kind of historian, in the context in which he was relating his histories he was as much an entertainer as much as a historian so he repeated every fun and weird story he heard. He did qualify the dog-headed men specifically as a thing he had heard in a ironic Greek tone, he was relating an entertaining tale, not trying to persuade you that dog-headed men really exist.