Hi @FredrikLindberg ,
Do you import necessary PowerApps modules successfully within your PowerShell window? How do you import it?
Which endpoint do you want your PowerShell script to run on? USGOV endpoint?
I have made a test (PowerShell version 5.1.17763.316), but has a different issue with you. I would post this issue to my product team, if the issue is solved, I would reply here.
Currently, I found an alternative solution to fix this issue. Before you type 'Add-PowerAppsAccount' command within your PowerShell window, please execute the following two commands firstly:
Set-ExecutionPolicy -ExecutionPolicy RemoteSigned -Force
dir . | Unblock-File

The whole steps for install PowerApps PowerShell cmdlets as below:
1. Execute the following commands firstly:
Set-ExecutionPolicy -ExecutionPolicy RemoteSigned -Force
dir . | Unblock-File
2. Import necessary modules:
Install-Module -Name Microsoft.PowerApps.Administration.PowerShell
Install-Module -Name Microsoft.PowerApps.PowerShell -AllowClobber
3. Add your PowerApps account:
Add-PowerAppsAccount /* <-- Open a dialog to provide your credentials */
Or
Add-PowerAppsAccount -Username foo@bar.com -Password $pass
Note: Please run your PowerShell as Administrator.
On your side, please consider upgrade your PowerShell server to the latest version, then re-start your PC, try it again, check if the issue is solved.
Also please consider take a try to install your PowerApps cmdlets within your PC based on the following article:
https://docs.microsoft.com/en-us/power-platform/admin/powerapps-powershell
Best regards,