Updating a local table with a per-row count(*) which is an aggregate of inner joins on remote server
Depending on your permissions, the linked server could be trying to stream all the data over locally and then doing filtering. References


Performance implications of using OPENQUERY in a view
Which one is more efficient: select from linked server or insert into linked server?
http://blogs.msdn.com/b/psssql/archive/2009/09/02/distributed-queries-remote-login-permissions-and-execution-plans.aspx


You might be able to skip that pain by computing the total aggregate count first into a table on the local server and then beat against that.

CREATE TABLE #LOCAL
(
    package_uuid nvarchar(255) NOT NULL PRIMARY KEY CLUSTERED
,   [count] bigint
);

INSERT INTO
    #LOCAL
SELECT 
    p.package_uuid
,   count(d.external_identification) AS [count]
FROM 
    ServerB.DATABASE.dbo.package p
    INNER JOIN 
        ServerB.DATABASE.dbo.doc2 d
        ON p.package_id = d.package_id
GROUP BY 
    p.package_uuid;


Try running that query locally on ServerB first to get an understanding of the theoretical throughput without factoring in your network. You can then do some quick and dirty estimates based on data sizes (500 + 8 per row in temporary table) and then it depends on your network. Hopefully this is all local network.

If the time is significantly different between the run on ServerB and pulling it back over, then you might need to use the OPENQUERY syntax to force the join on the remote server. Code approximately

CREATE TABLE #LOCAL
(
    package_uuid nvarchar(255) NOT NULL PRIMARY KEY CLUSTERED
,   [count] bigint
);

INSERT INTO
    #LOCAL
SELECT
    OQ.package_uuid
,   OQ.[count]
FROM
    OPENQUERY(ServerB,
    N'
    SELECT 
        p.package_uuid
    ,   count(d.external_identification) AS [count]
    FROM 
        DATABASE.dbo.package p
        INNER JOIN 
            DATABASE.dbo.doc2 d
            ON p.package_id = d.package_id
    GROUP BY 
        p.package_uuid
    ) AS OQ;