Eu faria o UPDATE primeiro, caso contrário você atualizará as linhas que acabou de inserir
SELECT .. INTO #temp FROM (shredXML)
BEGIN TRAN
UPDATE ... FROM WHERE (matches using #temp)
INSERT ... SELECT ... FROM #temp WHERE NOT EXISTS
COMMIT
Eu também consideraria mudar o XML para uma tabela temporária e usar SQLBulkCopy. Descobrimos que isso é mais eficiente do que analisar XML geralmente por mais de algumas centenas de linhas. Se você não pode alterar isso, você fragmenta o XML em uma tabela temporária primeiro?
