sysbench 0.4.12 with options:
--mysql-table-engine=innodb
--test=oltp --oltp-table-size=10000000 --oltp-point-selects=0 --oltp-simple-ranges=0 --oltp-sum-ranges=0
--oltp-order-ranges=0 --oltp-distinct-ranges=0 --oltp-index-updates=0 --oltp-non-index-updates=0
--max-requests=0 --max-time=300 --num-threads=2, 4, 8. 16, 32

for 2 threads get approx 1200 tps and 0 deadlocks, but for 4, 8, 16, 32 get ~200 tps and steadily increasing numbers of deadlocks (10 up to 297).

Innodb status for deadlocks shows:
------------------------
LATEST DETECTED DEADLOCK
------------------------
110915 18:30:47

• • • (1) TRANSACTION:
      TRANSACTION 12F6E6, ACTIVE 28 sec, process no 5598, OS thread id 140207001040640 starting index read
      mysql tables in use 1, locked 1
      LOCK WAIT 3 lock struct(s), heap size 1248, 2 row lock(s), undo log entries 1
      MySQL thread id 70, query id 3110358 localhost mysql updating
      DELETE from sbtest where id=?
    • (1) WAITING FOR THIS LOCK TO BE GRANTED:
      RECORD LOCKS space id 0 page no 54 n bits 144 index `PRIMARY` of table `bench`.`sbtest` trx id 12F6E6 lock_mode X waiting
    • (2) TRANSACTION:
      TRANSACTION 12BBA9, ACTIVE 53 sec, process no 5598, OS thread id 140207769769728 fetching rows
      mysql tables in use 1, locked 1
      36824 lock struct(s), heap size 3586488, 2724783 row lock(s)
      MySQL thread id 62, query id 3066651 localhost mysql Updating
      UPDATE sbtest set k=k+1 where id=?
    • (2) HOLDS THE LOCK(S):
      RECORD LOCKS space id 0 page no 54 n bits 144 index `PRIMARY` of table `bench`.`sbtest` trx id 12BBA9 lock_mode X
    • (2) WAITING FOR THIS LOCK TO BE GRANTED:
      RECORD LOCKS space id 0 page no 39541 n bits 144 index `PRIMARY` of table `bench`.`sbtest` trx id 12BBA9 lock_mode X waiting
    • WE ROLL BACK TRANSACTION (1)

A run with identically configured mariadb 5.2.7 elicits no deadlocks for any of the 2-> 32 threads.