Aside from the need to add licensed series specific pieces, how does LEGO decide it's time to introduce a new shape to the element palette?
This may not really qualify as an answer, but basically I believe designers are responsible for calling for new parts.
For each new part, a production cost is calculated, which takes into account a lot of factors. There were talks a few years back about how they had recently changed these rules, but they aren't public (to the best of my knowledge). What is more or less certain however is that an element which fits well in the system has considerably more chance of being accepted; that is, I suppose the calculated cost is lowered to reflect its usefulness. That's why a lot of recent new parts are just of the "it so obviously makes sense, why didn't they do that before"-kind (1x3 tile, 1x1 bricks with 1 knob,...).
So the designer willing to commission a new part for one of his sets will need to support that cost as part of the cost of his set, which is imposed to him. I guess there are much more rules than that (if multiple designers agree on a part, for example), but that's the basics of it.
Also, note that producing an existing part in a new colour follows the same rules to an extend, its calculated cost is higher than an existing colour for that part.
To summarize: each existing part has an associated production cost which the designers must take into account when creating a set. Non-existing parts are similarly associated a cost, which is calculated according to a lot of rules/factors which aren't public.
Even the costs of existing elements show subtle variations: some colours are cheaper than others, for example; or older elements may be more expensive because moulds aren't optimized (the known case is the Technic axle 5 which is cheaper than the 4 one, because there are twice as many of them on a mould).
Last thing, more as an aside: the cost of the first part in a model is also higher than the next ones, because it helps production to have more similar parts (that's why a model featuring 1x2 bricks with groove may not feature any regular 1x2 bricks in the same colour if it's not required)
Edit: here is a very interesting video on how they do prototype the new elements. Notice at the beginning of the video, the designer explicitely mentions he couldn't get the shape he wanted with existing elements, so he had to have a new one made. This was for a license set (cars), so again the decision in this case may be easier to take.