Single DELETE statement deadlocking in Sybase ASE
Original post describes a classic deadlock scenario with a twist, namely, a single DELETE ... WITH statement, which acquires 2 different kinds of locks.

Recommendation - change table from All Page Lock (APL) to Data Row Lock (DRL) scheme


clustered index will be replaced by placement index separate from data page
index access / updates will use latches rather than logical locks
row-level deadlock conflict is less probably (than page-level's)


Both SPIDs are executing the same sproc with the 1st DELETE ... WHERE statement demanding 2 different kinds of locks:


initially an UPDATE lock on a page when scanning for a row to delete (UPDATE lock is compatible with shared locks only but not with another UPDATE lock or exclusive lock);
once a target row is found on a page, then the UPDATE lock must be upgraded to an exclusive lockbefore deleting that row. 


The DEADLOCK events posted in your original question confirm the scenario : 


SPID 134 has held an exclusive lock on a page while waiting to acquire an UPDATE lock on another page i.e. it has deleted at least one row already and is continuing with searching for another (row to delete); 
SPID 166 blocks the first SPID's acquiring an UPDATE lock on a page while waiting to apply an exclusive lock on another page, which has an exclusive lock held by SPID 134 already (after deleting 1 row or more).