Thank Wolfgang Maier for reminding this issue and providing various details and observations. Having taken a look at my old comments (and at others' comments, too), I feel that the cwd issue deserves a clearer description.

Let's use the following simple C program as the callee:

#include <stdio.h>
#include <unistd.h>
int main(int argc, char* argv[]) {
    char cwd[FILENAME_MAX+1];
    for (int i = 0; i < argc; ++i)
        printf("argv[%d] = %s\n", i, argv[i]);
    getcwd(cwd, FILENAME_MAX);
    printf("cwd = %s\n", cwd);
    return 0;
}

As is evident, this program merely prints its arguments and working directory. I have built it using gcc, called it "print_argv+cwd", and placed it in the "subdir" subdirectory of the current directory.

Next, let's use the following Python 3 script for testing:

import os
from subprocess import run  # substitute run->call in Python < 3.5
prg_name = 'print_argv+cwd'
if os.name == 'nt':
    prg_name += '.exe'
else:
    prg_name = os.path.join('.',prg_name)
dir_name = 'subdir'
def execute(path, cwd):
    print('Executing "{}" in "{}":'.format(path,cwd))
    try:
        run([path], cwd=cwd)  # substitute run->call in Python < 3.5
    except Exception as err:
        print(type(err).__qualname__+':', err)
print('Script\'s cwd =', os.getcwd())
execute(prg_name, dir_name)
execute(os.path.join(dir_name,prg_name), dir_name)
execute(os.path.abspath(os.path.join(dir_name,prg_name)), dir_name)

Output on Linux with Python 3.5.2:

Script's cwd = /home/jenda/Bug reports/Python/subprocess
Executing "./print_argv+cwd" in "subdir":
argv[0] = ./print_argv+cwd
cwd = /home/jenda/Bug reports/Python/subprocess/subdir
Executing "subdir/./print_argv+cwd" in "subdir":
FileNotFoundError: [Errno 2] No such file or directory: 'subdir/./print_argv+cwd'
Executing "/home/jenda/Bug reports/Python/subprocess/subdir/print_argv+cwd" in "subdir":
argv[0] = /home/jenda/Bug reports/Python/subprocess/subdir/print_argv+cwd
cwd = /home/jenda/Bug reports/Python/subprocess/subdir

Output on Windows with Python 3.5.2:

Script's cwd = C:\Users\Jenda\Bug reports\Python\subprocess
Executing "print_argv+cwd.exe" in "subdir":
FileNotFoundError: [WinError 2] Systém nemůže nalézt uvedený soubor
Executing "subdir\print_argv+cwd.exe" in "subdir":
argv[0] = subdir\print_argv+cwd.exe
cwd = C:\Users\Jenda\Bug reports\Python\subprocess\subdir
Executing "C:\Users\Jenda\Bug reports\Python\subprocess\subdir\print_argv+cwd.exe" in "subdir":
argv[0] = C:\Users\Jenda\Bug reports\Python\subprocess\subdir\print_argv+cwd.exe
cwd = C:\Users\Jenda\Bug reports\Python\subprocess\subdir

Summary: On Linux, subprocess.run (or call or Popen) behaves correctly, in accordance with current documentation. On Windows, both possible relative paths produce incorrect results. With the first one, relative to "subdir", Python fails to find the executable. With the other one, relative to the script's cwd, Python actually executes the program, but argv[0] is inconsistent with cwd. Imagine that the called program wants to resolve its own path: It joins cwd and argv[0] and gets "C:\Users\Jenda\Bug reports\Python\subprocess\subdir\subdir\print_argv+cwd.exe", which is an incorrect (and nonexistent) path. This is why the cwd issue is not just a documentation issue.

The only option working correctly on Windows is the last one, using absolute path of the executable.