Some programs cannot be removed via add/remove when they are running. Try disabling your auto protect before running add/remove. If that doesn't work, try taking it out of your Startup menu - things that are loaded when Windows launches. Make sure you are NOT online when doing this since you will obviously no be protected once it is disabled & removed. If you need further instructions, you can PM me.
Try other methods before just deleting the McAfee folder, though. You can leave bits & pieces behind that way.
Just curious - are you changing to another anti-virus program? If so, which one?