Removing numbering gaps in a series of filenames
This is actually a very tricky function to write well, especially for a beginner.

Bugs

Be careful whenever you do string interpolation: escaping is often needed.  Here, you have plopped prefix directly into your regex, without considering whether there might be characters within the prefix that might have special significance in the regex language.  Here, you need to call re.escape().

if fileList is empty, you'll get stuck in an infinite loop, since Completed will never be set to True.

You probably want to require all of the filenames to start with the prefix.  Instead, you do re.search(), which performs an search that is not anchored at the beginning of the string.  You should use either re.match() or include a ^ at the beginning of your regex.

You zero-pad the numbers so that they are all the same width, based on the width of the number in the smallest-numbered file.  If the numbers are all the same width, then that's fine.  However, if they might not all be the same width, then it makes more sense to go with the width of the largest-numbered file.

Also, it's not obvious what the right behaviour is if spam1.txt and spam001.txt both exist.  Maybe that isn't a concern for you, but I thought I should mention it.

Algorithm

Your strategy works well enough for small numbers.  I wouldn't recommend it for a files named like photo_2016022235959.jpg — it could take a while to count that high!  Sorting might be a better strategy than counting up from 0.

The nested while True: for filename in fileList: loops are cumbersome.  You can often avoid loops in Python by using list comprehensions and generator expressions.  An additional benefit of using comprehensions and generator expressions is that you can "say what you mean" instead of specifying what to do step-by-step.

There is some repetition of the string-analysis code in the two loops.  I recommend performing the regex match once and storing the match results instead of the filenames.

Implementation details

I don't see any reason for converting folder to an absolute path.

os.path.isfile(…) involves a system call, and is much more expensive than a regex test.  Therefore, you should reorder the tests to do the quick test first:

if prefixRegex.search(item) and os.path.isfile(os.path.join(folder, item)):


However, since Python 3.5, you can use os.scandir() instead of os.listdir() if you also want information about the entries such whether it is a regular file (thus rendering the previous point moot).  os.scandir() produces os.DirEntry objects as results, such that you can retrieve the entry.name of the file and test entry.is_file() efficiently.

Instead of zero-padding numbers by concatenating strings yourself…


# New number including prefixed zero's
subNumber = '0' * (length - len(str((Number)))) + str(Number)
# New filename with updated number
newFileName = prefixRegex.sub(r'%s%s\4' % (prefix, subNumber), filename)



… use str.format():

'{}{:0{width}}.{}'.format(prefix, n, extension, width=width)


That means, basically, prefix + str(n) + '.' + extension.  A :05 format spec makes the number zero-padded to five digits; writing it as :0{width} makes it take the width from the parameter named width.

Counting loops are often better written using enumerate().

PEP 8 is the official Python style guide.  The naming conventions say that you should use lower_case_with_underscores for function and variable names.  Following some other capitalization convention is allowable if you need to interoperate with existing code, but is not recommended.

Suggested solution

import os, re, shutil

def fill_gaps(folder, prefix):
    filename_re = re.compile(r'{}(\d+)\.(.*)'.format(re.escape(prefix)))
    name = lambda match: match.group(0)
    number = lambda match: int(match.group(1))
    ext = lambda match: match.group(2)

    # A list of regular expression matches for all filenames that fit the
    # pattern, sorted numerically. filter(None, ...) eliminates false values,
    # namely the failed re.match(...) calls that returned None.
    matches = sorted(filter(None, (
        filename_re.match(entry.name)
        for entry in os.scandir(folder)
        if entry.is_file()
    )), key=number)

    if not matches: return

    first_num = number(matches[0])
    width = max(len(match.group(1)) for match in matches)

    for n, match in enumerate(matches, first_num):
        old_name = os.path.join(folder, name(match))
        new_name = os.path.join(
            folder,
            '{}{:0{width}}.{}'.format(prefix, n, ext(match), width=width)
        )
        if new_name != old_name:
            if os.path.exists(new_name):
                raise FileExistsError(new_name)
            # print('mv {} {}'.format(old_name, new_name))
            shutil.move(old_name, new_name)


I'd rather have the operation fail than risk overwriting an existing file, so I've added the test if os.path.exists(new_name): raise FileExistsError(new_name).