Knowing that someone reliable will always catch one when one falls doesn't make falling any less scary - for me, at least - especially so when one is falling from 10 or 15 meters from the ground. That's probably more than the distance beyond which my uncorrected myopic eyes can no longer distinguish facial features.
There actually is a term to describe the fear of falling from a high place: bathophobia. In fact, there is a word describing any fear you can think of - http://phrontistery.info/phobias.html - even fear of falling down the stairs (no, I don't have it, although I've never yet met a flight of stairs on which I'd not fallen down)
Two fears - that of heights and of falling from a high place - must somehow come together. I don't imagine there are many who are afraid of falling from a great height, yet don't mind being perched up high. It makes even less sense for someone to be afraid to be elevated, but do not mind falling off from there. Mind you, I use the word "fear", as opposed to phobia. Phobia implies irrationality, and although I feel it is hardly irrational to fear plunging down, possibly to death, the fear I intend to write about isn't intense enough to qualify for that term. So, the two fears - I have them both, I'm afraid. (Is there a phobia of phobias? Like, the irrational fear of being afraid of everything?)
I was first asked to overcome my fears by going up the bouldering wall beyond my comfort fall-level, and let go. Owing to one very insistent, I did, although I was immensely terrified and embarrassed (you would be too, if an involuntary squeal accompanies every fall). When I started top-roping, every time I felt I was going to slip, or felt I would likely not succeed making the next move, I'd shout a warning (or more accurately, an outright demand) to my poor belayer to really tighten the rope. With the rope absolutely taut, a fall isn't really a fall. Over time, I learned to completely trust my harness, the rope and the one holding it, and I was able to climb less noisily.
However, when it comes to leading, I've come to understand that I have no choice but to embrace falling. Suddenly, I find that I am afraid to attempt moves which, if it was a top-rope, I'd probably done without a second thought - for the rope must be slack, and if I fall, I'd really fall a long way. Clearly, if I were to pursue lead-climbing, this fear must be overcome.
He said it is common, in climbing training, to practice falling. Thus, we did, in small increments in the magnitude of the fall. First, we let go immediately after clipping the rope to a quickdraw, then halfway up between the last and the next one, and lastly, just before making the next. These falling exercises do help condition my mind to not respond with panic, which is crucial in preventing injuries. That said, giving notice to my belayer - "I'm gonna fall now!" - just before letting go sort of sets the exercise back a little. One day, I will, I hope, gain enough courage and confidence to just let go without warning, nor stealing a glance at him to ascertain he's paying attention and will not fail to catch me when I fall. He said I must, however, be careful not to attempt it when we're in company of any hot female climbers.
Yikes. OK, I have been warned.