大量にアイテムが保存されたリストの問題
大量にアイテムが保存された SharePoint Online リストをギャラリーコントロールにバインドした際、次のようなエラーメッセージが表示されることがあります。
また、このときのギャラリー コントロールの Items プロパティは、次のようになっています。
SortByColumns(Filter(Threshold, StartsWith(Title, TextSearchBox1.Text)), "Title", If(SortDescending1, Descending, Ascending))
タイトル列（Title）に対して操作が行われていることがわかります。どうやらこの操作が失敗しているようです。
このときに利用されている PowerApps 関数の SortByColumns 関数と Filter 関数（関数内で指定されている StartsWith 操作）は、いずれも SharePoint Online をデータソースとした場合、委任可能な関数となっています。
Delegable data sources in canvas apps
https://docs.microsoft.com/en-us/powerapps/maker/canvas-apps/delegation-list
つまりは、SharePoint Online 側の設定に問題がありそうです。
SharePoint Online リストに列インデックスを作成する
SharePoint Online の対象のリストにアクセスし、「リストの設定」を開きます。
列セクションの下にある「インデックス付きの列」を開きます。
「新しいインデックスの作成」を開きます。
「タイトル」を指定してインデックスを作成します。（今回は SortByColumns 関数や Filter 関数で利用している列がタイトルなのでタイトルを指定しています）
インデックスの作成処理がはじまります。「（インデックスを作成中です）」の表示が消えるまで待ちます。
動作を確かめる
インデックス作成完了後、PowerApps のアプリでデータ更新をすると、今度はエラーが返ることなく表示されます。
フィルターも動作します。
さいごに
PowerApps アプリで SharePoint Online リストをデータソースとする場合、同じようなエラーが発生したときは SharePoint Online リストの列インデックスの設定も確認してみてください。
ちなみに、今回の検証は、SharePoint Online のリストに 20,001 アイテムが保存された状態で行いました。