When using Rekognition, if you previously saved 1 million images in a Collection and do a SearchFaceByImage of 1 new image against those 1 million images, do you need to pay for 1 million API calls?

See the "Pricing example 2 – Multiple APIs and Face Detection" section in the Amazon Rekognition Pricing page.

You will need to pay: (1) 1 million images * IndexFaces + (2) face meta data storage = 1 million faces metadata objects x $0.00001/face per month + (3) 1 new image * SearchFacesbyImage

Once the faces are indexed, you don't need to run the IndexFaces again. The information will be stored as metadata.