Ok, if you're sitting in the car and you press the dash switch to lock the doors, how long does it take for the doors to lock? If it's about the same, then it's something to do with the locking mechanism.
If it's much faster then it's the BCM's response to the remote. Since the reset didn't help it's more likely to be an electrical fault, like a poor earth or slightly corroded connection. Check around pins 50-60 of the BCM (just spray the whole bloody lot don't sit there for 3 hours counting them while your a$$hole neighbour shouts out "13 ... 17 ... 26 ... 7 ... " to annoy you). Electrical contact cleaner = good stuff. WD-40 is ok too.
There are no relays involved, the BCM is wired directly to the door solenoids. You can grab a multimeter and test that the BCM is doing it right. When the doors are all closed, press LOCK and you should see 5V on pin 32, 0V on pin 34. Press UNLOCK and those two should reverse. If there's a delay there, and you've cleaned things up, maybe the BCM is faulty. Changing it means re-registering the keys - obviously possible, just a little time consuming.