Failed to create branch 'branchName': 4:Deadline Exceeded."

I'm getting an error Failed to create branch 'branchName': 4:Deadline Exceeded." when I try to create a branch on a significantly big commit (666 files modified lol) using Gitlab GUI or Gitlab REST API.

Creating branch using standard git client push works ok, but I found this because of failures from automation via REST API. Also all above methods work fine when creating branches on smaller commits.

Requests are failing after around 55 seconds.

My version is Gitlab v16.11.10

What I have tried already:

• I checked the logs, but I can't find any errors reported, just INFO logs about my requests, their time and error mentioned above.
• I tried increasing the "gitaly timeout" to 70s in /admin/application_settings/preferences#js-gitaly-settings , but this doesn't seem to have any effect, requests still fail after ~55s.

Any ideas? Is this a bug of some sort?