"Shoes mended while you wait" is not really a complete sentence. The intent is "We will mend shoes while you wait" or perhaps "Shoes are mended while you wait". But as others have noted, it's a common phrase used in advertising to mean that a service will be performed quickly enough that you can reasonably just stay at the shop and wait for it to be done rather than go home and come back at some time in the future.
Now that I think about it, if you wanted to push it, the literal words don't really promise anything. If the cobbler will take 3 weeks to fix my shoes, I COULD sit in front of his shop and WAIT for him to finish, bring a blanket and sleep there, etc. Or if I go home, I am still "waiting" for him to finish the job even if I do other things while I wait. But of course what they mean is that the job will be done within a reasonable waiting time, maybe half an hour or an hour.
Oh, and I should add, there's an implied passive here: the shoes WILL BE mended. Or an implied subject, "THE ELVES WILL mend your shoes". The shoes aren't mending anything.