Short enough not to interfere with other things.
Based on the scant information provided, there are zero or more possible restrictions on execution time.
That it recurs periodically, isn't a reason to require it shorter than that.
Examples:
Maybe there's little or no penalty for failure: maybe a display flickers, or there's a momentary hiccup in a slow control loop, or a delayed or dropped packet in a UDP application.
Maybe it's just a timer that schedules work to be done, and most of the time it returns immediately, but occasionally it takes much longer to finish (due to various reasons: external data, internal sequencing, etc.). And maybe that work must be done. So it just continues until it finishes. And in the mean time, the interrupt is skipped, or queued, or just keeps on running on top (the shorter passes finishing and returning to the longer run).
Thinking of things in terms of threads of execution, and concurrency, is useful, if a somewhat advanced topic. I'm guessing discussing it won't be of immediate help, but introducing the concept and getting accustomed to it is.
Interrupts are a rather basic primitive, almost not worth thinking in terms of threads -- you can't create and destroy interrupts arbitrarily, and you might not be able to delay or sleep them, as such -- but the other aspects are no less relevant, concurrency in particular.
Indeed, the latter case (a recurring interrupt that is allowed to overlap itself) can be considered a source of concurrent threads, placed on the stack, and running in order until they finish (equivalent to cooperative multitasking). You need to make very sure, of course, that the actions of each instance do not overlap and corrupt each others' state (including non-atomic / multi-word accesses that might get interrupted in the process). Use buffers/queues, mutexes, etc. to manage shared objects.
As for the usual case, you want to handle a minimum in the interrupt itself, and handle the rest in main() loop, or at least a lower priority interrupt. Example: put serial data into/out of a buffer, and interact only with the buffer from elsewhere.
I've also done before, an interrupt which dominates CPU usage. This must be done carefully, at low enough priority that it doesn't block other functions, but driven by a high enough priority interrupt for the hard real-time application. The XMEGA happened to have the right combination of features to do it:
https://github.com/T3sl4co1l/Reverb/The ADC samples come into an accumulator (unnecessary, turns out the XMEGA ADC is pretty clean), which is copied down periodically (ADC samples counted by a timer-counter). This gets a sample out of the super fast accumulator loop and into main memory. The timer fires a low-priority interrupt halfway between (every 4 samples, either the accumulator value is copied and reset, or the copy is processed), and this allows the processing to happen over a longer time scale without delaying others. In this way I can use, like, >90% of CPU cycles in that interrupt, without requiring main() to loop at high frequency (25kHz).
Tim