This seems like a good use case for using the OFFSET clause... Something along theses lines.
Note: because you're sorting on the clustered key, there should be no sort operation in the execution plan.
IF OBJECT_ID('tempdb..#test_data', 'U') IS NOT NULL
BEGIN DROP TABLE #test_data; END;

CREATE TABLE #test_data (
    oddly_spaced_id BIGINT NOT NULL,
    update_val INT NULL
    );

WITH
    cte_n1 (n) AS (SELECT 1 FROM (VALUES (1),(1),(1),(1),(1),(1),(1),(1),(1),(1)) n (n)),
    cte_n2 (n) AS (SELECT 1 FROM cte_n1 a CROSS JOIN cte_n1 b),
    cte_n3 (n) AS (SELECT 1 FROM cte_n2 a CROSS JOIN cte_n2 b),
    cte_Tally (n) AS (
        SELECT TOP (1000000)
            ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
        FROM
            cte_n3 a CROSS JOIN cte_n3 b
        )
INSERT #test_data (oddly_spaced_id)
SELECT DISTINCT
    ABS(CHECKSUM(NEWID()) % t.n) * t.n
FROM
    cte_Tally t

ALTER TABLE #test_data ADD PRIMARY KEY (oddly_spaced_id);

--==============================================================

DECLARE
    @total_rows INT = (SELECT COUNT(1) FROM #test_data td),
    @position INT = 0;

WHILE @position < @total_rows
BEGIN
    WITH
        cte_get_batch AS (
            SELECT td.update_val
            FROM
                #test_data td
            ORDER BY
                td.oddly_spaced_id
            OFFSET @position ROWS FETCH NEXT 10000 ROWS ONLY
            )
    UPDATE gb SET
        gb.update_val = @position
    FROM
        cte_get_batch gb;

    SET @position = @position + 10000;

END;

SELECT TOP 20000 * FROM #test_data td ORDER BY td.oddly_spaced_id;