First a nitpick: the 350 A heating system you describe is shorting the catenary, just not by earthing the normal 'working' voltage. Your system is certainly practical, especially if it is DC; I suspect some Nordic countries use something like that.

For the electric part of your calculation, I can only give slightly different numbers which don't result in changes of magnitude. For a European catenary type, let's take Re200, with a maximum 0.15 Ω/km (and as low as 0.04 Ω/km if there are parallel lines). For ormondotvos's Swedish example, the voltage is 15 kV; and we can easily assume 3 MW, giving us 200 A. That's 6 kW/km. In the extreme case of IORE locos (those double locos on the photo downthread) working at full power (10.8 MW, hence 720 A), we get 77.76 kW/km.

However, I am less sure about the first part of your calculation. I think we should be calculating heat flows rather than amounts of heat. One kilometre of 100 mm² wire has a surface of 35 m² (ignoring the carrying wire here), ice has a minimum thermal conductivity of 2.22 W/mK at 0°C. So even in the IORE case, for steady state, the temperature of the wire needs to rise above that of the air on the other side of the ice only by the numerical value of the width of the ice coat in millimetres (assuming it's uniform). To melt the ice, you really need a burst of power.

_{*Lunatic*, n.
One whose delusions are out of fashion.}