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 extent. It's 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 (one 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. For example, 7945 Fire Station doesn't have any regular 1x2 red or white bricks - since they have 1x2 bricks with groove for the doors, they used these everywhere a 1x2 was required - even if no groove was needed. That way the number of different parts in the set is lower.
Edit: here is a very interesting video on how they prototype the new elements. Notice at the beginning of the video, the designer explicitly 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.