The guaranteed overhead is in size, because JO has either 1 or 5 extra bytes per overflow check, compared to INTO. If you want the exception place to be known precisely, the program counter must be saved separately for each check, which adds a few extra bytes per check (e.g. 5 extra bytes for a CALL instruction, which allows the use of a short JO, so there are 6 extra bytes per check in total). Because there are many checks in a program, the extra program size is non-negligible.
The execution time should be about the same for INTO and JO, both for the normal case, when both INTO and JO are ignored and for the error case, when JO is guaranteed to be mispredicted, so its long execution time added to the time needed to fetch and execute the following instructions required to match the effect of an INTO (e.g. saving state and a second not-predicted jump or call that might be needed to reach the actual exception handler) will also be about the same as what would have been needed by an INTO exception, if not longer.
If this was really a concern, it would have likely not been deprecated in the move to 64-bit, and would have had support in other architectures as well.
And if you're really worried about size, "JNO 1f; INT xy; 1f:" 'with xy having to be system wide and well known, but it would only take 3 extra bytes (or just 2, if you HLT and the OS knows what JO/HLT combo means). The branch predictor will likely predict this as a no-take in any tight loop.
Almost all older architectures, except the very low-end CPUs like the 8-bit microprocessors, had integer overflow exceptions, not only divide-by-zero exceptions, so they did not need any instruction like INTO.
Other architectures, like IBM POWER, have much more powerful conditional trap instructions.
The 64-bit ARM ISA is the only other important architecture where integer overflow must also be done by combining a conditional jump either with a function call or with a supervisor call (i.e. the equivalent of INT).
It is true that if INTO would have never been defined in 8086, it would not have been a great loss, because it can be emulated, as you say.
Nevertheless, its deprecation by AMD cannot be a reason for praise. At the same time, they have also deprecated a few other instructions, which were a good choice, because they were much less useful. On the other hand there were a very large number of other instructions that could have been deprecated instead of INTO, which were much less useful than INTO, but they have been kept nevertheless.
It was pretty clear that INTO and BOUND were not included on the deprecated list based on their degree of usefulness but mainly because it was obvious that the CPU designers will be able to get away with this, because all the important software companies were habituated to compile their release versions by choosing to disable all run-time checks, so they will not complain about this omission.
If the software vendors would have ever been punished for choosing to omit the error checks, then they would have requested CPUs that still have good performance when the checks are enabled and the CPU designers would have been prodded to improve such features.
Nowadays, due to the hype about security flaws, the CPU vendors are introducing a large number of run-time checks, but most of them seem rather misguided, because in the attempt to protect against programming errors some of the methods used e.g. for limiting the targets of jumps also prevent the use of certain good implementation techniques for some programming language features.
Instead of the many dubious new "security" features of Intel/AMD and ARM CPUs, I would much prefer to see improvements in the efficiency of overflow checking and bounds checking, because these are checks that are required in any program, no matter how well it is written, while most of the new "security" features are mostly useful to avoid problems created by programmer mistakes.
