An easy first guess as to efficiency would be O(n) for insertions and deletions, since that's what you need to maintain a sorted list (which is the lowest level of a skip-list).
It doesn't have to be a linked list though. There are other purely functional sequence data structures which support O(log n) insertion and deletion, e.g. Haskell's Data.Sequence, which is a finger tree of some sort. If you could find a way to do binary search on one of these in better than O(log^2 n) time you'd pretty much have your purely functional skip list.