At the moment they're cleaned using alcohol wipes which I don't think is sufficient.
Our customer requires us to have a record that shoes have been cleaned once a week. In the meantime though I am putting together an argument against the requirement!
You don't think cleaning with alcohol wipes is sufficient, but you're also putting together an argument against cleaning the shoes? 
Out of curiosity, have BRC mentioned anything about your current practise in previous audits? AFAIK for low risk they require only footwear that can easily be cleaned so it sounds as though your customer's requirement is the limiting factor.
Wellingtons and a welly wash would be an alternative method of course if financial and practical barriers are not an issue, though likely exceeding requirements.