I suggest you bring this up in an office hour with the security review team and see what they suggest to be sure that your app won't fail the security review process.
Now to answer it,
Server to Server invocation
Usually the risk is very low if your connection is secured HTTPS from a theoretical perspective. In theory HTTPS connection does encrypt the url parameters.
If you are doing it in apex and your secrets are in protected custom metadata or settings I think it's ok.
A note to service provider of the API
The service can be invoker via a client side JavaScript. Hence service provider should change to use a POST instead of GET calls.
Example in the browser if screens are recorded then one can see the url parameter or in the browser history this will show up and the credentials are then compromised if browser is shared.
Also logging client secret and client in the sever via debug logs can be risky. If server is not protecting these logs and they show up then this is a big security risk.
I would reach back to external service provider and ask them to change to POST calls to mitigate any security risks.