Have you seen an actual entry in a register of baptisms? If you haven't, then there are various possibilities.
He might not have been born in Barnsley, although he says that in census returns.
He might have been born a couple of years either way of 1870 - FreeBMD has a number of Walter Wallers born between 1868 and 1872. If you are calculating his year of birth from a marriage or death certificate, or a census, these ages are not always absolutely accurate.
He might have been registered under a different spelling, although there are no Walter Woller births on FreeBMD between 1868 and 1872.
Walter may have been a middle name which he used instead of his first name.
If he were illegitimate, he might be registered under his mother's surname.
If you find him in the 1871 and 1881 censuses, that might help discount some of the above.