How to index two tables for JOINed query optimisation
For starters, get your LEFT JOIN right and try to get rid of total rows (as discussed in comments):
Query
Updated to your comment:

I only want to returns rows from request_logs that have a parallel entry in response_logs with non nil status:

SELECT q.uuid
     , s.status
     , q.method
     , q.requesturi
     , q.accessed
     , q.payload reqpayload
     , s.payload respayload
--   , COUNT(*) OVER() AS total_rows  -- see below
FROM   request_logs q
JOIN   response_logs s USING (uuid)   -- not LEFT JOIN
WHERE  q.accountid = 2
AND    q.requesturi NOT ILIKE '/v1/sessions%'
AND    q.accessed BETWEEN '2018-01-01 15:04:05 +0' AND '2019-01-02 15:04:05+0'
AND    q.applicationid = 1
AND    s.status IS NOT NULL           -- see below
ORDER  BY q.accessed DESC
LIMIT  1001;                          -- see below

Your LEFT [OUTER] JOIN burns down to a plain [INNER] JOIN. Related:

Query with LEFT JOIN not returning rows for count of 0

COUNT(*) OVER() AS total_rows is expensive for counts substantially bigger than LIMIT (and you are expecting &quot;10m+ rows&quot;). Maybe it's good enough to use LIMIT 1001, only use the first 1000 rows, check the row count and if it's 1001 then you know there are &quot;more than 1000 matching rows&quot;. Related:

Best way to get result count before LIMIT was applied

Indexes
If (like you commented)

the only 'moving parts' in this query are the dates (from and to) that are compared with accessed

... and more than a few rows are excluded with the other predicates
on applicationid, requesturi and accountid, then a partial index should help read performance (a lot):
CREATE INDEX ON request_logs (uuid, accessed DESC)
WHERE  accountid = 2
AND    requesturi NOT ILIKE '/v1/sessions%'
AND    applicationid = 1

And if a substantial percentage of rows is eliminated by status IS NOT NULL, also:
CREATE INDEX ON response_logs (uuid)
WHERE  status IS NOT NULL;

It may pay to append the columns status and payload as index columns if you can get index-only scans out of it. Some preconditions apply.