Why doesn't time for a simple update scale linearly with the number of records?
If you post the execution plans there may be obvious differences that we can highlight. Other than plans it could be:


Different distribution of values in the dataset, leading to more frequent page splits
Data and or log file growth
A sort or hash operation spilling to tempdb
Contention with other workloads


Need more information (queries, sample data, schema, plans) for better answers.