The reason these rent-a-cops are usually infuriating and not in the slightest bit intimidating is that they selectively choose to enforce the most insignificant, petty rules at the most inappropriate moments just to prove to themselves that they still have any sort of power or that they're not completely irrelevant.
Examples of this include the situation the above writeup describes (although going shoeless in a public place is a borderline unhealthy thing to do -- your feet may be clean, but just imagine what other people's shoes have tracked onto that floor!), a mall cop scolding you for walking the "wrong way" in an otherwise completely empty line or hallway, or for remaining in an area for "too long" (he'll call it "loitering", you'll call it "waiting for my wife/girlfriend to finish shopping in that store over there").
Mall cops are normally intended to assist business owners and law enforcement in protecting the mall's property, and the property of its tenants. With most stores employing their own security equipment (those annoying pedestals that beep when you leave the store, exploding dye tags, etc.) and sometimes even their own security staff, and with real police officers making frequent appearances at malls when needed, a mall cop's job gets pretty boring.
They respond to this by not-to-subtly harrassing people they don't like, judging solely on appearance, or rarely, on some random act of harmless teenaged mischief. They follow people (in an obvious manner) through the mall if they look weird. They try to stop people who try to take pictures of anything (with either a camera or a camcorder). They randomly approach teenagers, even those who are actually buying something, and demand to know what they're doing. They attempt to wield power when they honestly have very little.
Mall cops, like other rent-a-cops, tend to have no actual powers or authority above that of any other company employee. In many cases they have no form of specialized training to help them do their jobs. They are not real police officers, and as such have no legal authority to arrest or otherwise detain a person, even if a mall cop witnesses a crime. "Regular people" know this, and resent mall security for being a bothersome nuisance that slows down and detracts from the shopping experience. Criminals know this, and barely even factor in mall cops into their plans to shoplift and pickpocket people. Mall cops know all this, and quickly learn to hate their jobs and their powerless position, stop caring about their work, and treat everyone with equal disdain and distrust.
Special care must be taken to avoid these creatures when a local ordinance actually does grant some kind of official power (Nevada casino security personnel are legally permitted to detain and question anyone suspected of committing a crime, for example), because abuse of that power is common.