While the character design is Miyazaki's own, the name comes from Mei's mispronunciation of troll, from the story 3 Billy Goats Gruff. This is a fairly well known fact for Japanese moviegoers, as the evidence is in the movie itself. One of the shots in the closing credits show Satsuki, Mei and the mother reading a copy of this book, so we know where the name comes from:
The Japanese wikipedia article states that in earlier drafts, Totoro's name was Miminzuku, and is 1302 years old. Here's an early sketch, from back when Satsuki was not yet a character (and Mei was 5):
There is a good blog post about this stuff at a Japanese blog, but you kinda need to know Japanese to read it.
Edit: The plot thickens! Recalling something from somewhere, I remember how someone remarked that Totoro was based on an owl. Well, that would be pretty wild speculation if it weren't for a breed of owl to be known as Mimizuku (ミミズク) in Japanese. It's pure speculation that this is the main influence for the design, but y'know, he does sit in trees and hoot...