IntModulus long addition and subtraction
Small improvements

Overall, it seems that what you wrote is correct and is an improvement over the mod(mod(x)+mod(y)) solution, especially in the case where there is no overflow.  I have three small improvements:

Add instead of multiply by 2

You can replace this line:


   long result = 2L * mod(half) + lsb;



with:

    long halfmod = mod(half);
    long result = halfmod + halfmod + lsb;


The modified version showed a 1% improvement in the overflow case.  (See benchmarks below)

Remove one unnecessary check

Following the code above, you have this code:


    // Now the result lies in the range 0 to 2*modulus+1 (both included),
    // so conditionally reduce it twice.
    if (result&gt;=modulus) result -= modulus;
    if (result&gt;=modulus) result -= modulus;



But actually, the value of mod(half) is in the range 0..modulus-1.  So if you multiply that by 2 and add 1, result will be in the range 0..2*modulus-1, not 0..2*modulus+1 as you stated in the comment.  Therefore, after the first result -= modulus, the range of result will be 0..modulus-1 and there is no need for the second check.

    // Now the result lies in the range 0 to 2*modulus-1 (both included),
    // so conditionally reduce it once.
    if (result&gt;=modulus) result -= modulus;


By removing the second check, I found a 1% speed improvement in the overflow case.

Checking for overflow

I replaced this overflow check for add:


   final boolean overflow = (x^y) &gt;= 0 &amp; (x^sum) &lt; 0;



with this very similar one:

    final boolean overflow = ((x^y^Long.MIN_VALUE) &amp; (x^sum)) &lt; 0;


Edit: Later I found that this inverted version is faster:

    final boolean overflow = ((x^y) | ~(x^sum)) &gt;= 0;


It tests the same thing but uses one extra xor instead of a comparison.  For the overflow case I found a 2% speed improvement, and it was about 4% faster in the non-overflow case.

For subtraction I did a similar thing:


   final boolean overflow = (x^y) &lt; 0 &amp; (x^diff) &lt; 0;



became:

    final boolean overflow = ((x^y) &amp; (x^diff)) &lt; 0;


Here I didn't even have to add an extra xor.

Benchmarks

I took the suggestion of using JMH to run benchmarks.  Here are the results:

Overflow add test
-----------------
Methodology: Add 0x4000000000000000L with itself modulo 0x12345678
             in a loop of 100000 iterations. 

Method                   Operations per second     Speed
------                   ---------------------     -----
Original code              238.754 +- 0.778        100.0%
Multiply change            241.527 +- 0.884        101.1%
Remove extra check         241.180 +- 1.007        101.0%
Change overflow check      243.335 +- 1.662        101.9%
All changes                256.452 +- 1.325        107.4%

Non-overflow add test
---------------------
Methodology: Add 0x4000000000000000L with 1 modulo 0x12345678
             in a loop of 100000 iterations. 

Method                   Operations per second     Speed
------                   ---------------------     -----
Original code              330.298 +- 1.635        100.0%
Change overflow check      342.496 +- 2.037        103.7%