Can UPDATE lead to deadlocks in SQL SERVER? Can we experience deadlock if run the same update query concurrently?
Let's assume there's a table with millions of records and we need to update several thousand records at one shot.
UPDATE TABLEX
SET Column1 = '1'
WHERE Column2 BETWEEN 1 AND 10000

I'm wondering if running this query concurrently would lead to a deadlock as each update query may acquire update locks on rows in a different order.
In other words, is the following a possible scenario. The scenario is that two concurrent sessions run the same query to update the same set of records.
(My assumption is that each UPDATE statement will scan rows in a different order)

Session 1: Acquires Update lock on row 1 (Column2 = 1)
Session 2: Acquires Update lock on row 2 (Column2 = 2)
Session 1: Tries to acquire Update lock on row 2 but it fails as it's already held by Session 2. (Column2 = 2)
Session 2: Tries to acquire Update lock on row 1 but it fails as it's already held by Session 1. (Column2 = 1)
Deadlock is detected.

Here, my assumption is that each query may scan rows in a different order which implies locks on rows (resources) will be taken in different orders. Does this lead to a deadlock?
Here, my assumption is that each query may scan rows in a different order which implies locks on rows (resources) will be taken in different orders.

The scenario, as you've outlined it, is unlikely under normal circumstances.  The exact same query being run concurrently will most likely use the same execution plan - which means they will both scan the index on TABLEX in the same order.  This situation would most likely lead to blocking rather than deadlocks between the two identical queries.
This assumes you have an index on Column2 that can be used to seek to the right spot, and then scan the subset of rows that need to be updated.
If you don't have an index on Column2, you could end up with a parallel scan of the index / table, and thus your updates could be in an indeterminate order.  Consider a plan like this:

The order of rows coming out of the clustered index scan will vary depending on how many cores are being used by the plan, and how busy each core is doing other work - as well as disk-related waits and things like that.  Unless the &quot;gather streams&quot; is order-preserving, the rows will be updated in a sort of random order.  This could lead to deadlocks as you've described.
In summary, the answer to your question depends on several factors, including the details of your table / indexes, isolation levels, server and database level settings, etc.  Hopefully this gives you some idea of what's involved though.