GOSUB would put the calling location on a stack so you could RETURN to it later but there was no stack for parameters, local variables or return values so you had to use global variables for all of those.
You could not write recursive functions in BASIC unless you implemented a stack yourself using arrays. It was easy to compute Fibonacci iteratively, but people had to sort in BASIC all the time and wrote bubble sort, shell sort and other algorithms that were slow but easy to code in BASIC as opposed to Quicksort.
If you have the kind of functions that exist in C, Pascal, LISP, ML, Python and many other languages then you can write a simple Quicksort in a few lines of clear code.
One of the things many people fail to understand when they criticize GOTO and GOSUB is that it is essentially an expression of what is happening at the hardware level. Modern languages didn't really do away with them. They simply added a layer of abstraction that made it easier to develop reliable software. Unfortunately that abstraction also has overhead, which as problematic when you had a few kilobytes of RAM to work on with early personal computers. I would imagine that it was also problematic on the early multi-user systems that BASIC originated on. It isn't that GOTO is evil. It simply became less necessary for developers to use it in high level languages as technology improved.
Of course, the other thing that made spaghetti code inevitable was the line number based syntax. Until development tools improved, people were basically plopping new statements in random locations because they needed more "space" between existing statements. Yet line numbers were used in early systems since the BASIC REPL also served as a line editor. (At least on personal computers. I'm not sure how it worked on mainframes.)
If you added a bit more RAM than that you had more of a choice, for instance a 16K Color Computer could run
https://www.cocopedia.com/wiki/index.php/EDTASM%2B
editing programs with a text editor, saving them on cassette tapes, assembling them, etc. In the same amount of RAM you could have fit a FORTH implementation and with a disk system you could have an experience similar to BASIC based around editing individual disk blocks. With 64k of RAM I would run a C compiler on that color computer and people did the same with CP/M.
So far as mainframes at first they didn't have text editors, instead you would put together a deck of punched cards and submit that to the FORTRAN compiler which would output the object code to another deck of punched cards.
It wasn't unusual for people in the 1980s to use BASIC preprocessors that would read a text file, append line numbers, and let you use structured loops, and GOTOs with named labels. I read about
https://www.pcjs.org/software/pcx86/lang/other/ratbas/1982/
and wrote one for my TRS-80 Coco. It was the sort of thing you could write in BASIC without a lot of understanding about how to write compilers.
The problem, which you even mention, is that it's impractical to work with larger programs because their control flow becomes too hard to understand. Now, if you have (as many of the earlier BASIC systems did) only 4096 bytes of RAM you can't write such complex programs anyway, you don't have enough RAM. But even by the time these 4K home computers start to appear on the market the price of a modest business computer is tumbling, and such a computer might have dozens of kilobytes of RAM.
Once a flow diagram you can draw on a whiteboard isn't a correct description of your whole program, but merely a high level summary, go-to is just a foot gun.
goto is perfectly fine if used right. Kernel C code tends to use a lot of goto, to consolidate return points and to clean up resources on the way. A long function with no goto to one common return point, or multiple staggered ones, is suspicious.
The problem that led to the famous paper was rather that goto was abused, used at places where "higher level" control construct like "for", "while" and so on would be better. Partly because the languages just didn't have any, like for example... C64 BASIC.
Often within the scope of a function we would need to allocate/create dictionaries, arrays, other objects requiring disposal. MacOS's CoreFoundation API often returned NULL when creation (or insertion, etc.) failed. The sane thing to do when you got an unexpected NULL was to "bail" from the function. But rather than return immediately, there was clean up code at the bottom of the function — code like "if stackDict != NULL {CFRelease(stackDict);}". So we often added a label (called typically "bail") just before the clean up code and would "goto bail".
These were the days before garbage collection....
C64 BASIC has ingrained 1 evil in me. "goto" Atleast once a month I'll be working on some script and I'm stuck but a little voice in the back of my head will say: "a goto would fix this part you are stuck on!" And damn if that doesn't reverberate into the past.
I went the hardware route. I bought additional hardware for my C64. First the 1541 (5.25" floppy drive), then the 1581 (3.5" floppy drive), then a 300/1200 baud modem, then a 2400baud modem.
I've been hardware hooked ever since. I'm now a sysadmin working with *nix servers.
I tried programming. I really did. I meticulously copied one of the sample programs out of the back of the C64 manual. It never worked.