Others have noted that roads wear - an example of softer materials wearing harder one is liable to be useful.
If you look at centuries old stone stairs in Europe it is common to see a double indent shape worn by foot traffic. In the stairwell of the Leaning Tower of Pisa the stair indentations made by foot traffic have been filled with some protective substance (possibly many times) and are on their way once more to being worn into a double indent.
While both stairs and shoes wear, the rate of wear of the stone is no doubt such that the amount worn off in a climb is minimal - I'd doubt that you'd end up with a visible amount of stair dust coatings on the bottom of your shoes.
I took this picture in the 'Leaning Tower' in July 2003. You can see both the wear patterns in the stone and the added protective material:
Detailed crop. Larger image