Pagination performance, with subquery, inner join and where
I don't think you'll be able to get good performance while using OFFSET.  The database must search through 1,000,025 rows of output from the inner query; even if you have a good clustered index on TaskResults the system doesn't know for certain that it can skip ahead to date X.

But you do!  Assuming this is for some kind of GUI, make a note of the earliest StatusDate from the previous query, then use it to fitler next page:

SELECT
    tr.Id, StatusDate
FROM
    (
    SELECT tr.Id, tr.StatusDate
    FROM mon.ArchivedTaskResults_201504 as tr WITH (NOLOCK)
        INNER JOIN mon.ViewDevicesWithGroups dev WITH (NOLOCK) ON tr.DeviceId = dev.Id
    WHERE tr.ClientId = 4 AND dev.Deleted = 0
        AND
            (
            -- Retrieve only records from before the previous page
            tr.StatusDate &lt; @PrevStatusDate
            OR (tr.StatusDate = @PrevStatusDate AND tr.Id &lt; @PrevID) 
            )
    ) AS tr        
ORDER BY StatusDate, Id DESC
FETCH NEXT 25 ROWS ONLY


So if page #123 ends with 2015/05/01, record #234, you want to consider all records that are from 2015/04/30 or earlier, or which are also from 2015/05/01 but are for records #1 .. #233.

This should work well with your more complex UNION query, but "real" partitioning would probably be easier than this roll-yer-own partitioning..

If StatusDate is unique, or it's acceptable to occasionally show the same record on two adjacent pages, you can drop the @PrevID and ORDER BY Id bits.  If Id is always-increasing, you can filter off of it and skip StatusDate.

Keep in mind that retrieving pages like this can easily skip a record or include the same record twice if records are being adding, removed, or reordered in the underlying data.  But that's another topic.