Thanks, everybody, for the detailed and helpful answers!

alexsms: (can you say lace the laces in English, by the way?)
Absolutely, but the meaning would most often be similar to the definition that CoffeeCup gives here:

расшнуровать / зашнуровать - are used when a shoelace is taken totally out (or inserted in the lace holes when it was totally out) of the shoe.
So one would typically say "lace the laces" (or "lace the shoes") if you are putting the shoelaces in the holes of new shoes, or replacing a broken shoelace. Otherwise, "(un)tie the (shoe)laces" or "(un)tie the shoes" sounds more colloquial.