Short answer: forever and ever!
Long answer: when your leg falls asleep, the sensory nerves get pinched so you can no longer feel sensation below the compressed nerve. However, this does not necessarily cut off blood supply! You might have observed that when a limb falls asleep, there's no indication of it turning colors or changing temperatures, and that is because the blood vessels supplying the nerve are not necessarily as compressed as the nerve itself. Theoretically, you could stay there for hours and hours (or the whole night, as most of us have experienced) and once you finally untangle yourself, the nerve becomes uncompressed and you will usually restore normal sensation within an hour.
Should circulation actually be cut off, however, most evidence points to 2-4 hours before a limb starts to die. It's definitely a much shorter time in the brain, though! Brain cells tend to start dying within 5 minutes of oxygen deprivation, so don't let your head fall asleep!
