Como usar a variável SQL para iterar nós XML

Seu próprio código funcionaria com apenas mais um [1] . A função .modify() não pode interpretar o [sql:variable(...)] ... Este pode ser qualquer filtro, mesmo um com mais de um resultado... Então, basta alterar isso para:

DECLARE @xml xml = '<Root>
                      <Contacts>
                        <Contact name="John Doe" type="REG" other="value" />
                        <Contact name="Jane Doe" type="REG" other="value" />
                        <Contact name="Jennifer Doe" type="REG" other="value" />
                        <Contact name="Jane Doe" type="REG" other="value" />
                      </Contacts>
                    </Root>';
DECLARE @i int = 1
SET @xml.modify('replace value of (/Root/Contacts/Contact)[sql:variable("@i")][1]/@type with "NEW"')
SELECT @xml

Mas eu iria por outro caminho... Você pode ler tudo como uma tabela derivada e reconstruir o XML assim:

SELECT
(
    SELECT c.value('@name','nvarchar(max)') AS [@name]
          --,c.value('@type','nvarchar(max)') AS [@type]
          ,'NEW' AS [@type]
          ,c.value('@other','nvarchar(max)') AS [@other]
    FROM @xml.nodes('/Root/Contacts/Contact') AS A(c)
    FOR XML PATH('Contact'),ROOT('Contact'),TYPE
)
FOR XML PATH('Root')

Outra abordagem seria FLWOR:

SELECT @xml.query('
for $r in /Root/Contacts
    return <Root><Contacts>
    {
        for $c in /Root/Contacts/Contact
           return <Contact name="{$c/@name}" type="NEW" other="{$c/@other}"/>
    }
    </Contacts></Root>
')