user54011: I'm using a Nano. The code below is a simplified workup of my problem code. 
The point of it is asynchronous debounced button press detection. The actual code sets a volatile bool to tell the main loop it saw a press, but this simplified version toggles the state of the built-in LED. Another LED follows the state of the pushbutton to make it possible to see whether the ISR is firing appropriately. 
#define SHORT_PRESS_MS 50
#define PUSHBUTTON_PIN 2
#define BUILTIN_LED_PIN 13
#define OTHER_LED_PIN 12
volatile unsigned long fallTime = 0;
volatile int builtinLedState = LOW;
void isr_change()
{
    unsigned long now = millis();
    int pushbuttonState = digitalRead(PUSHBUTTON_PIN);
    // show switch state with LED and 120 Ohms on D12
    digitalWrite(OTHER_LED_PIN, pushbuttonState);
    if ((pushbuttonState == LOW) || (fallTime == 0))
    { // change to low => falling edge
        fallTime = now;
    }
    if (pushbuttonState == HIGH)
    { // change to high => rising edge
        long pressMs = now - fallTime;
        if (pressMs > SHORT_PRESS_MS)
        { 
            builtinLedState = !builtinLedState; 
            digitalWrite(BUILTIN_LED_PIN, builtinLedState); 
        }
    }
}
void setup()
{
    pinMode(PUSHBUTTON_PIN, INPUT_PULLUP);
    pinMode(BUILTIN_LED_PIN, OUTPUT);
    pinMode(OTHER_LED_PIN, OUTPUT);
    attachInterrupt(digitalPinToInterrupt(PUSHBUTTON_PIN), isr_change, CHANGE);
}
void loop() {}

When this runs, OTHER_LED slavishly follows the button. There is no perceptible lag and it never gets out of synch no matter how machine-gun my antics with the button.
However, toggling of the built-in LED is not reliable. That OTHER_LED remains in sync with the button state implies that the event is always firing and the state is always what I expect, so it seems like there is a problem with my attempt to measure time. 
What is the right way to measure time inside an ISR?

Applying suggested diagnostics confirmed the hypothesis of the accepted answer. Having determined the nature of the problem, I rewrote the ISR as follows.
void isr_change()
{
    static long fallTime = 0;
    static int lastPushbuttonState;
    int pushbuttonState = digitalRead(PUSHBUTTON_PIN);
    if (lastPushbuttonState != pushbuttonState)
    {
        long now = millis();
        if (pushbuttonState == LOW)
        { // change to low => falling edge
            fallTime = now;
        }
        if (pushbuttonState == HIGH)
        { // change to high => rising edge
            long pressMs = now - fallTime;
            if (pressMs > SHORT_PRESS_MS)
            {
                digitalWrite(LED_BUILTIN, !digitalRead(LED_BUILTIN));
            }
        }
    }
}

Testing reveals that the problem is resolved and the intended behaviour is occurring (reliably detect presses of minimum duration).
Also of interest is the use of static to carry values between ISR invocations with local scope, rather than using global volatile variables.

user7508: I cannot make sense of this:
if ((pushbuttonState == LOW) || (fallTime == 0))

Why || (fallTime == 0)? Other than this, your ISR looks fine to me.
And your way of measuring the time is correct. The only scenario I can
imagine that can make the toggling unreliable is the ISR missing
transitions, which can happen if the input pin gives very short spikes.
Here is my scenario:
The button is pressed, fallTime holds the correct value, you release
the button. At this point, the bouncing button generates a very short
positive pulse: LOW → HIGH → LOW. The first transition triggers an
interrupt request. However, there is some latency in handling the
request. By the time the ISR starts running, the pin has already toggled
back to LOW, and the ISR then incorrectly updates fallTime.
A little bit later, the pin toggles back to HIGH for good. However,
now is very close to fallTime, and the rising edge gets ignored.
You can check whether you have missed transitions by toggling the LED
every time you see the same state as in the previous ISR run:
void isr_change()
{
    static uint8_t previous_pin_state;
    uint8_t pin_state = digitalRead(PUSHBUTTON_PIN);
    if (pin_state == previous_pin_state)
        digitalWrite(LED_BUILTIN, !digiatlRead(LED_BUILTIN));
    previous_pin_state = pin_state;
}


54011: <p>I'm using a Nano. The code below is a simplified workup of my problem code. </p>

<p>The point of it is asynchronous debounced button press detection. The actual code sets a volatile bool to tell the main loop it saw a press, but this simplified version toggles the state of the built-in LED. Another LED follows the state of the pushbutton to make it possible to see whether the ISR is firing appropriately. </p>

<pre><code>#define SHORT_PRESS_MS 50
#define PUSHBUTTON_PIN 2
#define BUILTIN_LED_PIN 13
#define OTHER_LED_PIN 12
volatile unsigned long fallTime = 0;
volatile int builtinLedState = LOW;
void isr_change()
{
    unsigned long now = millis();
    int pushbuttonState = digitalRead(PUSHBUTTON_PIN);
    // show switch state with LED and 120 Ohms on D12
    digitalWrite(OTHER_LED_PIN, pushbuttonState);
    if ((pushbuttonState == LOW) || (fallTime == 0))
    { // change to low =&gt; falling edge
        fallTime = now;
    }
    if (pushbuttonState == HIGH)
    { // change to high =&gt; rising edge
        long pressMs = now - fallTime;
        if (pressMs &gt; SHORT_PRESS_MS)
        { 
            builtinLedState = !builtinLedState; 
            digitalWrite(BUILTIN_LED_PIN, builtinLedState); 
        }
    }
}
void setup()
{
    pinMode(PUSHBUTTON_PIN, INPUT_PULLUP);
    pinMode(BUILTIN_LED_PIN, OUTPUT);
    pinMode(OTHER_LED_PIN, OUTPUT);
    attachInterrupt(digitalPinToInterrupt(PUSHBUTTON_PIN), isr_change, CHANGE);
}
void loop() {}
</code></pre>

<p>When this runs, OTHER_LED slavishly follows the button. There is no perceptible lag and it never gets out of synch no matter how machine-gun my antics with the button.</p>

<p>However, toggling of the built-in LED is not reliable. That OTHER_LED remains in sync with the button state implies that the event is always firing and the state is always what I expect, so it seems like there is a problem with my attempt to measure time. </p>

<p>What is the right way to measure time inside an ISR?</p>

<hr>

<p>Applying suggested diagnostics confirmed the hypothesis of the accepted answer. Having determined the nature of the problem, I rewrote the ISR as follows.</p>

<pre><code>void isr_change()
{
    static long fallTime = 0;
    static int lastPushbuttonState;
    int pushbuttonState = digitalRead(PUSHBUTTON_PIN);
    if (lastPushbuttonState != pushbuttonState)
    {
        long now = millis();
        if (pushbuttonState == LOW)
        { // change to low =&gt; falling edge
            fallTime = now;
        }
        if (pushbuttonState == HIGH)
        { // change to high =&gt; rising edge
            long pressMs = now - fallTime;
            if (pressMs &gt; SHORT_PRESS_MS)
            {
                digitalWrite(LED_BUILTIN, !digitalRead(LED_BUILTIN));
            }
        }
    }
}
</code></pre>

<p>Testing reveals that the problem is resolved and the intended behaviour is occurring (reliably detect presses of minimum duration).</p>

<p>Also of interest is the use of <code>static</code> to carry values between ISR invocations with local scope, rather than using global volatile variables.</p>
 7508: <p>I cannot make sense of this:</p>

<pre class="lang-cpp prettyprint-override"><code>if ((pushbuttonState == LOW) || (fallTime == 0))
</code></pre>

<p>Why <code>|| (fallTime == 0)</code>? Other than this, your ISR looks fine to me.
And your way of measuring the time is correct. The only scenario I can
imagine that can make the toggling unreliable is the ISR missing
transitions, which can happen if the input pin gives very short spikes.</p>

<p>Here is my scenario:</p>

<p>The button is pressed, <code>fallTime</code> holds the correct value, you release
the button. At this point, the bouncing button generates a very short
positive pulse: LOW → HIGH → LOW. The first transition triggers an
interrupt request. However, there is some <a href="https://arduino.stackexchange.com/a/8926">latency</a> in handling the
request. By the time the ISR starts running, the pin has already toggled
back to LOW, and the ISR then incorrectly updates <code>fallTime</code>.</p>

<p>A little bit later, the pin toggles back to HIGH for good. However,
<code>now</code> is very close to <code>fallTime</code>, and the rising edge gets ignored.</p>

<p>You can check whether you have missed transitions by toggling the LED
every time you see the same state as in the previous ISR run:</p>

<pre class="lang-cpp prettyprint-override"><code>void isr_change()
{
    static uint8_t previous_pin_state;
    uint8_t pin_state = digitalRead(PUSHBUTTON_PIN);
    if (pin_state == previous_pin_state)
        digitalWrite(LED_BUILTIN, !digiatlRead(LED_BUILTIN));
    previous_pin_state = pin_state;
}
</code></pre>
