Tested on Samsung Omnia 2 with Sense 2.5 and everything is working fine.
The program is not a beta anymore, but still under development and may contains some bugs.

Features:
- Maximum 10000 pictures from multiple folders.
- Changeable interval from 10 to 720 minutes (12 hours).
- Chooseable user interface to change background (Today and Sense).
- Same wallpaper for the 2 UI or not.
- Start with Windows possibility.
- Not use memory at all, the changing starts with schedule and then quit.
- Separate settings application (only WVGA resolution supported yet).
- You can start/stop the scheduling in the settings app.

Special thanx:
mohitsapru for his help.

It is possible the program is working on other Sense, Manila or TouchFlo versions than Sense 2.5, if the wallpaper stored in the same place.

More screenshots here.

Update Description:
v1.4:
- No maximum files number anymore (maximum folders number is still 100).
- A "Change NOW interface" added to select the needed UI to the change.
- Now the settings app shows the next time of the schedule.
- Random and continuously change setting added (you'll see randomizing popup window sometimes).
- Intervals minimum set low to 1 minute with 1 minute steps.
- Besides the interval, now you can change the wallpapers at a specific time, like 8:00AM every day.
- The "back to the previous wallpaper" function is added and accessible with the "-prev" parameter and will change all choosen UI's wallpapers back to the previous one (not 100% if you use more than 1 directory for wallpapers storing).
- The installer creates a "Change Now" and "Previous wallpaper" shortcut.
- Because I cannot create a setup.dll, the additional shortcuts is downloadable from the bottom of this post, but you need to edit the files, if you're not install the app to the device.
- Several minor and major bugfixes.

v1.3:
- The program is now compatible with CHT 1.8.X. You can change the wallpaper of the Home tab, All tab and CHT Lockscreen.
- When you plug your phone to USB with Mass Storage settings, and the needed folder is not available to the WaPaC (or you deleted a selected folder), the app not crash.
- Context menu added to the Selected Folders list to remove folders (if the folder is not available anymore, etc.)
- The application is pops up a warning in the case you not select any UI, when you want to save the settings (not when you uncheck all).

v1.21:
- The folder changing bug fixed (when you tap on a folder and jumped to an other in the selected one).

v1.2:
- Redesigned interface.
- Separated setting for "Change on Windows start" (If you have an earlier version installed, then you need to uncheck and save, then recheck and save the "Start with Windows" option, because the shortcut contents is changed).
- You can choose Minutes or Hours format at Interval settings.
- Interval changed to 5-1440 minutes or 1 to 24 hours.
- "Change NOW" button added.
- "Change only in idle state" option added (This means, if you're using the phone (the backlight is on) in the time when the scheduled change comes, the changing is delayed).
- Maximum selectable folder number is 100.

v1.1ß:
- Folder selection is now free.
- Maximum picture number changed to 10000/folder.
- No need to refresh the list when you put new pictures in a selected folder.
- Selected folders list stored and displayed after start and easy to modify.
- You can add a folder to the selected folders list by checking the checkbox near the folder's name. You can remove by the same method.

The program's not listing the directories with the following names:
- Windows.
- Program Files.
- Application data.
- ConnMgr.
- Documents and Settings.
- Temp.

v1.03ß (1.02 skipped, because some real trouble):
- S2U2 background change added (not tested).
- Settings saving corrected (HKCU\Software\WaPaC\).
- Interval steps changed to 5 mins.
- Settings application supports all resolutions (tested on VGA, QVGA, WQVGA, WVGA, Square).

v1.01ß:
- Start with Windows option problem fixed.
- Clear Sense Background option added.