How would I approach creating "fall damage" in the game engine?
I don't know if you're accepting logic bricks answer, but you can simply have a property on the floor that the player can detect (or in some cases just sense for any collision at all). When the Collision sensor reads false, you can just make the player enter the "fall" state. You should be doing this anyway, so it won't be too hard to add a timer to sense how long the player has been airborne. You want to set it high enough so that the normal jump, or a jump slightly downhill doesn't activate it.

Next, remember, it's not falling that hurts people, but the ground. So when the player hits the ground, before wiping the timer, check the value. If it was over your fall limit, damage the player by a multiple of the remainder. (ie.falls 4 sec. limit was 2.5, multiplier was 3: damage the player by 7 health.) This is reliable, and the more you fall, the more you get damaged. Realistically, you would use an exponential function, but no-one likes falling 10 meters in a game and dying. 



In the .blend, practice dropping the man from different heights.