Salesforce REST API Query - URL Limit

I am currently using the Salesforce REST API to fetch the records from Salesforce by passing the query via the query parameter in the GET request. However, this particular implementation returns an error when the url query parameter character count is more than 16000. Is there a way to get it to accept around 1,00,000 chars in the url?

Unfortunately, it looks like you're just hitting the limits imposed by Salesforce:

SOSL search query strings

Maximum length of SearchQuery string

If the SearchQuery string is longer than 10,000 characters, no result rows are returned. If SearchQuery is longer than 4,000 characters, any logical operators are removed. For example, the AND operator in a statement with a SearchQuery that’s 4,001 characters will default to the OR operator, which could return more results than expected.

Source: https://developer.salesforce.com/docs/atlas.en-us.salesforce_app_limits_cheatsheet.meta/salesforce_app_limits_cheatsheet/salesforce_app_limits_platform_soslsoql.htm

I don't know the Salesforce API at all, but I have two suggestions (especially if no one else answers your question):

1. Investigate a POST/PUT based query option in the Salesforce REST API. I think I read something about being able to format a query in JSON and then submitting that instead (but I could be wrong). Edit: I looked a little more, and I didn't see anything immediately that said this was a possibility.
2. Use a less specific, and therefore smaller, query. If you're making this URL call from an application that you have control over (e.g., shell script, Java application, etc.), massage the data at that level and return a smaller subset of that data. If you're worried about getting too much data back at once, that shouldn't be a problem. It sounds like they limit the amount they send back per request and send a URL at the end of each response to the next page of results.