This is a guess (but should be a good guess, at that): try Bata Shoes. They're a big chain that is similar to Payless and have branches in many of the shopping centers.
Payless was here in Singapore but from a google search is not clear if they're still in operation.