Every Monday we will post an entry that hasn’t yet been published with a view towards harnessing the collective onomastic power of the internet. If you have any thoughts about the name’s origin, other variants it might be related to, other examples of its use, etc., please share them in the comments! If you wish to browse other Mystery Monday names, there is an index.
Since we’ve been revisiting Germanic themes recently, how about a round of “guess the prototheme”? The deuterotheme here is easy — Old Saxon wald, Old High German walt ‘power, authority’, but anyone want to hazard a guess at what the prototheme is? Leave your best guess in the comments!
Dictionary of Medieval Names from European Sources 
Could it be a *really* mangled version of Adal?
The prototheme is clearly Old High German hadu ‘battle’ with an -l extension of the stem (l-extensions are quite frequent and occur with many stems).
I concur with Jörg Knappen. Förstemann (Sp. 649) also has the early example Chadoloald. This turns out to be from Diplomata, chartæ, epistolæ, leges aliaque instrumenta ad res Gallo-Francicas spectantia, ed. J.M. Pardessus, Paris, 1849, Nr. CCCXXXI, CCCXXXII, from 658 CE, in both documents actually in the form Chadoloaldus. He also has it from about the same date in I papiri diplomatici, ed. Gaetano Marini, Rome, 1805, Nr. LXVI, in the inflected form Chadoloaldo, apparently the same person.
And obviously I wasn’t paying attention, since I now see that your examples are the first two of Förstemann’s citations.