Kevin,
Do you have good ventilation?
It is absolutely necessary to have continuous soffit venting and continuous ridge venting to prevent your problem. That way, the air temperature under the shingles will approach the outside temperature.
You are right, no amount of insulation will stop icicles from forming unless ventilation in the attic is sufficient.
Dodgeman