Number of locks exceeded when adding foreign key constraint
According to the MySQL Performance Blog


  Lets start with a bit of background – in Innodb row level locks are
  implemented by having special lock table, located in the buffer pool
  where small record allocated for each hash and for each row locked on
  that page bit can be set. This in theory can give overhead as low as
  few bits per row, so lets see how it looks in practice


The same reference brings this out...


  So we locked over 100K rows using about 44KB. This is still quite
  efficient using less than 4 bits per locked row. 
  
  In practice this means memory consumption by row level locks should not be
  the problem even for rather large databases – even billion of locked rows should
  take half GB of memory, which is small fraction of memory used on
  serious systems. Furtermore you would unlikely need or want to lock
  every row in your table/database which makes it even smaller problem.


Evidently, all 17 million rows need to be locked. Based on the link from mysqlperformanceblog.com:


100,000 rows takes 44 KB
17,000,000 rows should take 7480 KB, just over 7 MB


I can easily see an unconfigured innodb_buffer_pool_size (Default is 128M in MySQL 5.5, and 8M before MySQL 5.5) causing a problem.

OK Let's get back to your questions:


  Why exactly are there so many locks, i.e. what is being locked in this
  query?


Every row in an InnoDB table must be locked. This makes the data available via MVCC, ACID Compliance, and Transaction Isolation.


  Why didn't locking the table solve the problem? Do I need to do the
  lock in a different way or lock something else as well?


Same as Answer 1


  If the only solution is to increase the innodb_buffer_pool_size, how
  large does it need to be for this query?


There must be enough RAM to not only hold your working set of InnoDB data and index pages, but also small amount of overhead (44KB per 100,000 rows) for table locks.