Python 2, 124 120 bytes

X,Y=input() i=j=s=0 while i<len(X): v=abs(Y[j]-X[i]) if j+1<len(Y)and v>=abs(Y[j+1]-X[i]):j+=1 else:s+=v;i+=1 print s 

Try it online!

Saved 4 bytes by moving to program versus function.

Note that each time around the loop, either i is incremented or j is incremented. Thus the loop is executed at most len(X)+len(Y) times.

Python 2, 124 120 bytes

X,Y=input() i=j=s=0 while i<len(X): v=abs(Y[j]-X[i]) if j+1<len(Y)and v>=abs(Y[j+1]-X[i]):j+=1 else:s+=v;i+=1 print s 

Try it online!

Saved 4 bytes by moving to program versus function.

Meeting the time-complexity constraint is possible because both lists are sorted. Note that each time around the loop, either i is incremented or j is incremented. Thus the loop is executed at most len(X)+len(Y) times.

Python 2, 124 bytes

def f(X,Y):  i=j=s=0  while i<len(X): 	v=abs(Y[j]-X[i]) 	if j+1<len(Y)and v>=abs(Y[j+1]-X[i]):j+=1 	else:s+=v;i+=1  return s 

Try it online!

Note that each time around the loop, either i is incremented or j is incremented. Thus the loop is executed at most len(X)+len(Y) times.

Python 2, 124 120 bytes

X,Y=input() i=j=s=0 while i<len(X):  v=abs(Y[j]-X[i]) if j+1<len(Y)and v>=abs(Y[j+1]-X[i]):j+=1  else:s+=v;i+=1 print s 

Try it online!

Saved 4 bytes by moving to program versus function.

Note that each time around the loop, either i is incremented or j is incremented. Thus the loop is executed at most len(X)+len(Y) times.

Python 2, 124 118 bytes

def f(X,Y): i=j=s=0 while X[i:]: 	v=abs(Y[j]-X[i]) 	if Y[j+1:]and v>=abs(Y[j+1]-X[i]):j+=1 	else:s+=v;i+=1 return s 

Try it online!

Note that each time around the loop, either i is incremented or j is incremented. The loop completes when i>=len(X), and j cannot exceed len(Y); thus the loop is executed at most len(X)+len(Y) times.

Python 2, 124 bytes

def f(X,Y): i=j=s=0 while i<len(X): 	v=abs(Y[j]-X[i]) 	if j+1<len(Y)and v>=abs(Y[j+1]-X[i]):j+=1 	else:s+=v;i+=1 return s 

Try it online!

Note that each time around the loop, either i is incremented or j is incremented. Thus the loop is executed at most len(X)+len(Y) times.