Com o Acordo Ortográfico de 1990, já não se utiliza o hífen entre as formas monossilábicas de haver e de (Base XVIII do Acordo). Temos agora, portanto, há de se lhes perdoar.
Antes de o acordo ortográfico entrar em vigor, encontram-se as duas variantes quando haver de é seguido de clíticos. Um par de exemplos do Google Books:
- Hei-de lhe falar lugubremente (Cesário Verde, edição de 1992: link)
- Hei-de-lhes acabar com a manha de andarem atrás de mim! (Branquinho da Fonseca, edição de 1945, link)
Ou no jornal Público, que não aplica o Acordo Ortográfico de 1990:
- Há-de-se ver, mulher. Há-de-se ver. Respondia como sempre falava: há-de-se viver (link)
- Se acontecer, há-de se ver na altura (link)
- É por causa de Hollande, mas há-de-lhes passar. (link)
Não é óbvio que uma variante seja muito mais comum do que a outra.
Não consegui encontrar nenhuma fonte que apontasse para a correção de uma ou de outra forma. Em todo o caso, o teu argumento para rejeitar a união com hífen («"se lhes" [é] relativo ao verbo "perdoar" e não ao "haver de"») é problemático — não é óbvio que a afirmação seja verdadadeira. Os verbos auxiliares admitem subida de clítico, isto é, a ligação ao verbo auxiliar do pronome clítico complemento do verbo principal.
Não há dúvida de que haver de admite subida do clítico em construções com próclise:
Não lho hei de perdoar. (em alternativa a «Não hei de perdoar-lho»).
O que é extraordinário nos verbos auxiliares que regem a proposição de (haver de, ter de, acabar de), é parecerem não admitir o pronome em posição enclítica:
*Hei-lho de perdoar.
Nem sempre assim foi. Por exemplo:
Hemo-nos, senhores, de ir. (Camões, link)
Hás-me de jurar uma cousa que te não custará nada. (Herculano)
Casarás com o homem; mas já agora hão-se de festejar os teus dezassete anos em casa. (Camilo)
Modernamente, com as formas monossilábicas de haver, é inclusive pouco aceitável inserir qualquer elemento entre haver e de (cf. havemos um dia de lá ir com *hei um dia de lá ir), daí a antiga ortografia prescrever um hífen. Mas nenhum dos auxiliares que regem de aceitam um pronome unido ao verbo
auxiliar em posição enclítica (cf. ficou-me a dever, que não é problemático, e onde o auxiliar rege a). A Gramática do Português da Gulbenkian, na pág. 1242 (cap. 29, da autoria de Eduardo Raposo), dá estes exemplos:
a. ??Tenho-lhe de pagar alguma coisa, certamente.
b. *Ela há-me de encontrar nalgum momento.
c. ??O mordomo acabou-me de trazer o pequeno almoço.
Mas se o pronome estiver à direita de de (temos de lhe pagar, há de me encontrar, acabou de me trazer), as construções são aceitáveis. O autor sugere resolver a aparente anomalia dos auxiliares que regem de desta forma:
Para resolver este paradoxo, propõe-se aqui a hipótese de que a preposição de se "incorpora" no verbo auxiliar, formando com ele um grupo complexo unitário do ponto de vista morfológico. Ou seja, a preposição de é parte integrante dos verbos auxiliares (repare-se que, antes do Acordo Ortográfico de 1990, a ortografia codificava essa estrutura no caso do auxiliar haver (de), ao unir os dois itens com um hífen).
No entanto, como o autor reconhece (caixa 9) e como tu sugeres, esses casos também podem ser analisados como casos de próclise ao verbo principal.
Frases como "hei de lhe dizer" seriam então estruturalemente ambíguas entre casos de próclise ao verbo pleno e ênclise ao verbo auxiliar (unido com de). No primeira caso, faria mais sentido escrever há-de se lhes perdoar (tal como os brasileiros escrevem vou te perdoar, sem hífen, dado que se trata de uma próclise ao verbo principal), no segundo há-de-se-lhes. Como referi antes, ambas podem ser encontradas.