Lambdaは同一リージョン内での同時実行数が「1,000」で、
同期呼出の場合呼び出し時にMAXを超えた以降の処理はエラーになっちゃうんですよね。
SQS使って管理しろって言われるかもしれませんが、
できるだけ使用するサービス数は押さえてシンプルにさっぱり頂きたい。
というわけでなんとか楽をしたくて調べてみたところ、Lambdaを非同期で呼出せば同時実行数の上限から溢れたリクエストを再試行してくれると公式のドキュメントにありました。

同時実行数の管理
非同期でLambdaを呼出せば、イベントを最大6時間自動的に再試行すると書かれています。
というわけで今回はAPI GatewayをからLambdaを非同期で呼出してみることにしました。

API Gateway で AWS Lambda 関数の REST API を作成する
はい。こっちも公式ドキュメントにしっかりとやり方が書いていますね。
基本的に心を無にして↑に書かれている手順を辿ると非同期実行することができましたが、
ちょっとだけ難しいというか言葉足らずな書き方をしている箇所があったので、
今回はそこをポイントとして記載します。

####ARNについて
LambdaとロールのARNをAPI Gatewayの「統合リクエスト」へ登録しますが、
LambdaのARNについては追記する内容があります。

上記の画像の黒塗り部分はARNそのものです。
見て頂ければわかると思いますが、LambdaのARNの前後には「/2015-03-31/functions/」と「invocations」を加える必要があります。
ロールについてはARNをそのままコピー＆ペーストで大丈夫です。

####HTTPヘッダーについて

API Gatewayの「統合リクエスト」→「HTTPヘッダー」へは上記の設定が必要です。
気を付けたいのは「マッピング元」の「'Event'」で、これは「'」も含めた形で記載する必要があります。

####その他
API Gatewayの「モデル」については「Input」のみ登録すれば大丈夫です。
「Output」と「Result」は公式ドキュメントの手順では使用されません。

先述しました通り、基本的には公式の手順通りに進めれば問題なく実装できます。
ネットで調べると色々と記事が出てきますが、まずは公式の手順で作ってみることをお勧めします。