Wrapping query in IF EXISTS makes it very slow
As has been explained by Paul White in his blog post: Inside the Optimizer: Row Goals In Depth the EXISTS introduces a row goal, which prefers NESTED LOOPS or MERGE JOIN over HASH MATCH


  As a final example, consider that a logical semi-join (such as a
  sub-query introduced with EXISTS) shares the overall theme: it should
  be optimised to find the first matching row quickly.


In your query this apparently happens to introduce nested loops and remove parallelism, resulting in a slower plan.

So you would probably need to find a way to rewrite your query without using the NOT EXISTS from your query.

You might get away with rewriting your query using a LEFT OUTER JOIN and checking there wasn't a row in smalltable by testing for NULL

If EXISTS(
    SELECT databasename
    FROM somedb.dbo.bigtable l
    LEFT JOIN dbo.smalltable c ON c.source = l.source
    WHERE databasename = 'someval'
    AND source &lt;&gt; 'kt'
    AND c.source IS NULL
)


You could probably use a EXCEPT query too, depending on how many fields you need to compare on like this:

If EXISTS(
   SELECT source
   FROM somedb.dbo.bigtable l
   WHERE databasename = 'someval'
   AND source &lt;&gt; 'kt'

   EXCEPT

   SELECT source
   FROM dbo.smalltable
)


Mind you, Aaron Bertrand has a blog post providing reasons why he prefers NOT EXISTS which you should read through to see if other approaches work better, and to be aware of the potential correctness issues in case of NULL values.

Related Q &amp; A: IF EXISTS taking longer than embedded select statement