Velcro doesn't do well with pulling forces over a long period of time, and it doesn't do well with dirt and dust. We would all be adjusting our velcro all the time. Also shoelaces are easier to replace, and can be used to apply pressure to multiple parts of a shoe much easier than velcro. Think about shoes like converse or docs where they need to be held upwards and along the foot and leg shape, it would be very hard and annoying for velcro to do the same.