Deosil comes from Gaelic (both the Irish and Scottish forms, found as deiseil, deiseal and deasal), and means "right", being the direction one turns when going clockwise.
The spelling deosil though is rarely seen prior to Gerard Gardner, and is likely just his choice of how to spell a dialect word that had no set spelling (the OED lists deasil, deiseal, deisal & deisul). It holds the distinction of being the sole example of several "witch words" that he claimed were "seemingly Celtic" or from "some older tongue" that weren't in fact plain (if obscure) English words of Saxon origin. Gardner ne cuþe a Sax word gif it bat him in þe ærs (I'm probably getting that Anglo-Saxon very wrong, but I'm still better than Gardner).
Anyway, it still exists in Irish and Scottish Gaelic as a word meaning right (as in not left), right (as in not wrong), south (which is on your right as you face the direction of sunrise) and as a general exclaimed blessing ("may things go right").
It has nothing to do with the direction of the sun, as is often suggested (with people even suggesting that it means anticlockwise when one is sufficiently south of the equator).
Withershins is in fact a merging of two separate words, with overlapping meanings. The most direct ancestor would be widdersyns (and similar other spellings) which as you say (and show from etymonline) means "against the way" and hence contrary to the "proper" direction.
However, there was also once widersonnis, withersones, etc. where the second part of the word comes from sonne, sunne (sun) rather than sinnen (way, journey, direction), as with:
Sayand the said Margarat Baffour vas ane huyr and ane wyche and that sche ȝeid widersonnis about mennis hous sark alane.
(Claimed the aforementioned Margaret Balfour was a whore and a witch and went [in the direction contrary to that of the sun] around men's houses [wearing only a light nightshirt or shift which is a shocking state of undress to the people who spoke Middle Lowland Scots, and so they apparently needed a word for it, though its a right bugger to translate into Contemporary Modern English]).
Of course, the two words were close in both sound and meaning, and in some cases when we have forms like widdershines it's not even clear which it is. As such, the two formerly separate words merged into each other, and so we have one of the interesting cases where a word as two separate (albeit similar) etymological roots.
The pairing of the two is another etymological case in itself. Deosil is Scottish Gaelic (as well as being Irish) and as such predominately found in the Highlands. Widdershins is Scots word, predominately found in the Lowlands. This oversimplifies a lot, and even from that oversimplification, there is nothing to say that a borrowing wouldn't have led to both being used by the same people (I grew up with a dialect with borrowings from both Irish and Ulster-Scots, so I certainly won't claim it doesn't happen), but just how likely one was to find the two paired is unclear. A lot of the written records we have of both words are from English writers who are pointing out the words new to them as matters of interest in themselves, as they travelled in Scotland, which muddies the waters further.
Whether the two were much found together or not in 16-19th Century Scotland, as a pairing used in Contemporary Modern English, they originate with the Wicca and other Mesopagan and Neopagan practices. So too does the idea that they are "the old way" of talking about clockwise and counter-clockwise; in truth the old words for those rotational directions were right and left.