Stored procedure deadlocking itself, how do I resolve it?
Each of your 2 update statements may cause deadlock when executing within different transactions, no matter explicit or implicit.  They both change the same set of rows  , and nothing guaranties in which order the rows are locked.
One option is just to catch error and re-run failed transactions. Another approach is  to somehow "serialize" updates. 

In my opinion, the easiest and fastest way is to modify procedure so it waits until the other instance of the same procedure completes updates.  It can be implemented, for instance, by using sp_getapplock.  

Another option is to ensure that rows are locked in the same order (e.g. -open cursor that reads all required rows in particular (unique) order, iterate through it, and for each row issue SELECT WITH ROWLOCK), and issue update after all rows are locked.  Then in case of simultaneous execution the second transaction will wait for the first one. I think that for SQLServer a very little chance of deadlocks might exist because of potential lock escalation though.