Question: Is there a limit to the amount of contacts that can be searched for on Existing Contact using autocomplete on a Drupal Webform? I have 1+million contacts. If I restrict the webform to a group with a limited number of contacts the autocomplete works well. However, if I do not restrict to a small group the autocomplete fails and wants to create a new contact.

Answer: 
The autocomplete works and does not have a limitation (we have 900k contacts and no problems). My mistake was in the selection of the Contact Display Field for the Existing Contact on the Drupal WebForm. I was using the "Display Name" as the structure but I was entering search as if it was the "Sort Name" I was getting unexpected results. Once I started entering the search with the correct format the results were as expected and all the contacts are included.
There is no hard limit, no. You may need to dig in a bit more to find out why the search is not returning any results. Is it timing out? Or is it failing on permission checks?