sql server – Update query performance improvement (MS-SQL)

UPDATE M SET ARCHIVE_FLAG = 'N' FROM MARKPOSTED_TMP M WHERE
EXISTS (SELECT 1 FROM SHFMKPSTMM S INNER JOIN SHIFT_TMP S1 
ON M.MARKID = S.MARKID AND 
S.SHIFTID = S1.SHIFTID AND S1.ARCHIVE_FLAG <> 'Y') 

The above query is currently updating around 414163 rows in 44 seconds, And I want to improve its performance by maybe doing it parallel or updating in batch?

I have tried with the below query-

UPDATE M SET ARCHIVE_FLAG = 'N' FROM MARKPOSTED_TMP M WHERE
EXISTS (SELECT 1 FROM SHFMKPSTMM S INNER JOIN SHIFT_TMP S1 
ON M.MARKID = S.MARKID AND 
S.SHIFTID = S1.SHIFTID AND S1.ARCHIVE_FLAG <> 'Y') OPTION (MAXDOP 8);

But only with 4-6 seconds better result

Execution plan suggests index scan non-clustered on SHFMKPSTMM table is taking 49% cost. But I can’t remove the index from that table.

Any help in the better query formulation to improve the performance?