May one use the Instrumental case here? Я говорю скайпом з Марком.
I don't think so :-)
For "to speak on the phone" you can hear both variants: "говорити по телефону" and "говорити телефоном." I believe you can say it for Skype too.
Nope. Unless Skype is a language :) but in that case it would be different sentence in English