How can I improve this update?
As Ypercube said in his comment you seem to have an uncorrelated subquery.  This means that for each way you are trying to build a line containing 1,000,000 odd nodes.

Also it it would be best to put a Geography constructor around the result of the subquery.  

The tutorial's update statement that you referenced has got a correlated subquery, because the WHERE clause is wn.wayid = ways.wayid 
Changing your update query to this should fix the issue.

UPDATE ways
SET geog4326 = Geography::STGeomFromText('LINESTRING(' + STUFF((
    SELECT ',' + 
        CAST(CAST(n.Longitude AS decimal(18,9)) AS varchar(32)) + ' ' + 
        CAST(CAST(n.Latitude AS decimal(18,9)) AS varchar(32)) AS [text()]
    FROM ways w 
        JOIN waynodes wn ON w.wayid = wn.wayid
        JOIN nodes n ON wn.nodeid = n.nodeid
    WHERE wn.wayid = ways.wayid -- Changed to ways to correlate
    ORDER BY w.wayid, orderid
    FOR XML PATH(''), TYPE
    ).value('/', 'NVARCHAR(MAX)'),1,1,'') +')',4326)
WHERE EXISTS (SELECT 1 FROM waynodes wg WHERE ways.wayid = wg.wayid GROUP BY wg.wayid HAVING COUNT(*) &gt; 1)


Personally I prefer to construct my update statements similar to the following.

UPDATE z
SET geog4326 = Geography::STGeomFromText('LINESTRING(' + STUFF(CAST(x.linestring AS VARCHAR(MAX)),1,1,'') +')',4326)
FROM ways z
    CROSS APPLY (
        SELECT ',' + 
            CAST(CAST(n.Longitude AS decimal(18,9)) AS varchar(32)) + ' ' + 
            CAST(CAST(n.Latitude AS decimal(18,9)) AS varchar(32)) AS [text()]
        FROM ways w 
            JOIN waynodes wn ON w.wayid = wn.wayid
            JOIN nodes n ON wn.nodeid = n.nodeid
        WHERE z.wayid = w.wayid 
        ORDER BY w.wayid, orderid
        FOR XML PATH('')
    ) x (linestring)
WHERE EXISTS (SELECT 1 FROM waynodes wg WHERE z.wayid = wg.wayid GROUP BY wg.wayid HAVING COUNT(*) &gt; 1)


I've tested a SELECT version of my update on some made up data.
SQLFiddle

 WITH ways AS (
 SELECT *
 FROM (VALUES
    (1),(2),(3)
    ) W(wayid)
 ), 
 waynodes AS (
 SELECT *
 FROM (VALUES
    (1,1,1),
    (1,2,2),
    (1,3,3),
    (2,1,4),
    (2,2,5),
    (2,3,6),
    (3,1,7),
    (3,2,8)
    ) WN(wayid, orderid, nodeid)
 ), 
 nodes AS (
 SELECT *
 FROM (VALUES
    (1, 0, 0),
    (2, .1, 0),
    (3, .1, .1),
    (4, .1, .1),
    (5, .2, 0),
    (6, .3, 0),
    (7, 0, 0),
    (8, 0, .2)
    ) N(nodeid, longitude, latitude)
 )
SELECT Geography::STGeomFromText('LINESTRING(' + STUFF(x.linestring,1,1,'') +')',4326)
FROM ways z
    CROSS APPLY (
        SELECT ',' + CAST(CAST(n.Longitude AS decimal(18,9)) AS varchar(32)) + ' ' + CAST(CAST(n.Latitude AS decimal(18,9)) AS varchar(32)) AS [text()]
        FROM ways w 
            JOIN waynodes wn ON w.wayid = wn.wayid
            JOIN nodes n ON wn.nodeid = n.nodeid
        WHERE z.wayid = w.wayid 
        ORDER BY w.wayid, orderid
        FOR XML PATH('')
        ) x(linestring)