I have encountered "всевеликое войско донское", but what exactly does it mean in Russian? Perhaps it is dialectal? Can it be seen in other context?
It's a Church Slavonic calque from Greek παμμέγιστοσ ("the greatest of all").
The Greek word had been used as a title of several Christian saints in medieval Greek literature and was calqued by Slavonic translators.
The tradition of using a positive Slavic adjective and the prefix все- to form a superlative form can be also observed in words like всеблагий ("the kindest of all"), всемилостивый ("the most merciful of all"), всепетая ("the most praised of all") etc.
This pattern might be somewhat confusing because words like всемогущий ("omnipotent") and всеведущий ("omniscient") don't mean "the most knowledgeable / potent of all", but rather "the one who knows / can do everything".