3.6 and any 4/4.1 can be installed concurrently, but they can not be running concurrently.
You can install the 4.1 demo and then input your upgrade serial number from the box in the startup dialog. That was how I did my upgrade, except that I bought the upgrade serial number online from Adobe.
(LR4.1 upgrade will need both the serial number from your LR3.6 and the upgrade serial number for LR4. But if LR3.6 is already installed, it will find the LR3.6 serial number by itself, and you will just have to press OK.)
I'd like to add to Allan's post that once you have upgraded a 3.x catalog to 4.x you will not be able to use this very same catalog with 3.x anymore. However, LR 4 creates a copy of it when it does the upgrade so your 3.x catalog is safed to use it with LR 3.x.