Velcro doesn't rely on friction, but instead on a kind of adhesion. As you say, the force of friction is constant regardless of contact area, because large areas have more surface area but also lower pressure, since the weight is divided over a larger area, too. Adhesion is a different story, though. In adhesion, there is some other force holding the two surfaces from moving. In chemical adhesion (like glue), its chemical bonds. In physical adhesion (like with Velcro), it's the little hook-shaped plastic pins on one side holding onto the web on the other side. Either way, the force holding the two sides together does not depend on weight, so a larger area means a larger force to overcome if you want to move or remove the pieces.

Velcro is not held together by friction. Velcro consists of an array of tiny hooks that snag on the fibers that the Velcro is attached to. The reason why Velcro is difficult to pull apart is that, to do so, you must pull apart the chemical bonds that hold the fibers together (i.e. break them). The reason why Velcro depends upon area is because the more area, the more hooks there are to be snagged.