I found that the Spanish page
http://www.partosindolor.com/nombresnenas.htmand other pages list Deolinda as a shorter form of Teodolinda, and that in turn is explained on this Italian page
http://digilander.libero.it/gioer/lf.htmlas deriving from the two Germanic words that make up
Dietlinde.
I think together with the overall similarity of Deolinda and
Dietlinde this makes the derivation quite probable.