There are actually two mechanisms for reference counting. Shared DLL reference count is the "old" method which was brought in for the 16 bit versions of windows and also for NT to reduce "DLL Hell". This method is based on registry counts linked to the DLL name.
Windows Installer brought in a second method, reference counting by Component GUID, which happens automatically, and which is the functionality that Merge Modules rely on.
The Shared DLL reference counting method is actually a legacy method for non MSI installers, and ideally you would rely entirely on the component GUID method in any modern environment.
What I suspect may be happening is that your Component GUID count for the component(s) in question is not being decremented to zero during your upgrade thus causing the component to remain installed.
Before you spend too much time on this, can I check that you are testing on a clean build EACH TIME as residual components from previous attempts could cause this problem as well. Check also that none of your components are marked "Permanent" as that would also prevent them being removed at uninstall.

Solutions - the simplest to implement would be to use the RemoveFile table to explicitly delete the files in question before the upgrade is installed. With your RemoveExistingProducts action sequenced where you have it, the old app should be removed first, then the RemoveFile action will run, and finally the InstallFiles action will run, as that will be their sequence order (amongst other actions) in the InstallExecute sequence.
More complex would be to examine the registry keys for the component registration (which is stored using the rearranged form of the component GUID) and attempt to change any erroneous reference count there

Out of interest, does an normal uninstall of the original MSI result in all files being removed?  If not, then that would be the first item on my fix list, as identifying the reason for this will give you the best shot at the most elegant way of fixing this in your upgrade.

In an ideal world. files that are identical should have the same component GUID - that is the raison d'etre for merge modules as I'm sure you know, but the same technique can also be implemented manually in your projects if you don't want to create and manage merge module libraries specifically.  On the other hand, if the files are different in any way, then they must have a unique GUID. If you happen to have the same GUID on a component in your upgrade that is newer than the original, then that needs to be fixed.

One more thing I would check, is the registry table. If capture has been used at any time, it is possible that there is a registry key in the registry table that is directly modifying the reference count, instead of allowing windows to manage this. So check the registry table in both your merge module and in your main application for any registry keys that might be carrying reference count information, and if found, delete them.

Your log should record all activity, so if the deletion of the file is not recorded, then perhaps it is not being deleted for some reason. Putting a pause in your install after the RemoveExistingProducts action would allow you to check which files have been removed and which might still be there, before you allow the install to continue.
A pause is simple to implement using a Type 38 "Run VBScript from Embedded" custom action, containing a single line such as:
msgbox "Installation is paused", 4096, "PAUSED"
Just sequence the CA just after RemoveExistingProducts and the installation will display this message and wait for your OK before proceeding.

Thanks again for the help! 

Incidentally, for any future readers, the "pause" custom action needs value 38 rather than 4096 if it's between RemoveExistingroducts and InstallInitialize, and value 1062 (38+1024 = deferred) when it's after InstallInitialize.

The messy details boil down to ProcessComponents setting the refcount "wrong".  It's consistent from Win2000 through Win7, so I guess it's a feature by now, not a bug :-(

After RemoveExistingProducts ("REP") the files are correctly gone, and the SharedDlls refcount is gone too. Unfortunately, if the incoming new component cB (containing myfile.exe) uses SharedDllRefCount, the standard action ProcessComponent sets the new refcount up by one (ie to 2 if there's only the single app using the file).  Yuck.

I haven't poked into the windows-installer-native component reference management but believe that's correct, with only the SharedDlls count wrong, because when SharedDlls value is manually decremented to 1 the uninstall removes myfile.exe

> One more thing I would check, is the registry table. If capture has been used at any time, it is possible
> that there is a registry key in the registry table that is directly modifying the reference count

There's nothing relevant in the reg table; capture was never used.

I'm contemplating a custom action to "adjust" the refcount, but don't know how to differentiate between  the refcount value=2  because of this ProcessComponent feature and value=2 because there are two products installed which use myfile.exe.  I suspect there is no good, clean solution.  I'm also going to try some other installer forums for suggestions, so will post any brilliant idea here.

Alan

Now that you mention it, I do recall experiencing a similar issue on what was probably NT4 back then, and could not quite figure out what was causing the ref count to increment by two when only one instance was installed.
The simplest solution may be to check any current setting before Installinitialize, then increment the property by 1, and overwrite the registry key using a custom action conditioned to run on install only, after InstallFinalize.
However, if you do find a more elegant solution then please post it here!