And here's my AppleScript version -- I won't pretend it's perfect, but it works! It can be run standalone from Script Editor, saved as an app and triggered by KM, or it wouldn't take much work to use it in a KM macro, feeding in the source and target folders.
It's a bit more generic in that it will duplicate all files in the source folder -- you could easily limit the selection to eg mp4 files using a "whose" clause at line 13. You can easily change max folders, max files per folder, and destination folder prefix in the properties. There's an ersatz "progress dialog" after every folder is filled -- you can keep those on screen for longer by increasing the "giving up after" value.
It does mute your output volume so you don't get spammed with a dozen or more "copy completed" Finder boings every second 
Because it's generic there's a simple way to test it for a folder of files:
Make a new folder called "Source" on your Desktop
Make a new folder called "Transfer" on your Desktop
In Terminal, type cd ~/Desktop/Source;touch test file_{0001..9999}.txt
If you've got time to spare you can increase the "9999" to "66000" to test your max folders boundary
Note: I think the leading 0s in line 3 above are a zsh thing -- if you are using bash then miss them out
You can then run the script, selecting "Source" and "Transfer" as appropriate.
Summary
property maxFiles : 256
property maxFolders : 256
property targetFolderPrefix : "Transfer-"
set startTime to get current date
set targetList to {}
tell application "Finder"
-- pick the folders
set sourceFolder to (choose folder with prompt "Choose source folder")
set targetFolder to (choose folder with prompt "Choose or create target folder")
set sourceList to every file of sourceFolder
set numberOfFiles to length of sourceList
set numberOfFolders to round (numberOfFiles / maxFiles) rounding up
-- set up target structure
if numberOfFolders > maxFolders then set numberOfFolders to maxFolders
set theCount to 1
repeat numberOfFolders times
set newFolder to (make new folder at targetFolder with properties {name:(targetFolderPrefix & text -3 thru -1 of ("00" & theCount))})
copy {fileCount:0, targetFolder:newFolder} to end of targetList
set theCount to theCount + 1
end repeat
display dialog "Target folders created" giving up after 2
-- do the copying
-- you'll get Finder copy-done noise every file if you don't mute sound output!
set volume with output muted
set copyStartTime to get current date
set folderCount to 1
set targetFolderBase to (targetFolder as text)
repeat while length of sourceList > maxFiles and folderCount ≤ maxFolders
set destinationFolder to (targetFolderBase & targetFolderPrefix & text -3 thru -1 of ("00" & folderCount) as alias)
repeat maxFiles times
set i to get random number from 1 to length of sourceList
duplicate item i of sourceList to destinationFolder
set sourceList to removeFromList(i, sourceList) of me
end repeat
-- create and display progress report after each complete folder
set timeLeft to round ((((current date) - copyStartTime) / (folderCount * maxFiles)) * (length of sourceList) / 60) rounding up
display dialog "" & maxFiles * folderCount & " files copied out of " & numberOfFiles & "
" & timeLeft & " minutes remaining" giving up after 2
set folderCount to folderCount + 1
end repeat
-- and finish off the remainder
set destinationFolder to (targetFolderBase & targetFolderPrefix & text -3 thru -1 of ("00" & folderCount) as alias)
repeat with eachFile in sourceList
duplicate eachFile to destinationFolder
end repeat
-- reset sound and send alert
set volume without output muted
beep
set timeTaken to (get (current date) - startTime)
set {takenMinutes, takenSeconds} to {timeTaken div 60, timeTaken mod 60}
display dialog "Done. Took " & takenMinutes & " minutes and " & takenSeconds & " seconds"
end tell
on removeFromList(index, aList)
if index = 1 then
return rest of aList
else if index = length of aList then
return items 1 thru -2 of aList
else
return (items 1 thru (index - 1) of aList) & (items (index + 1) thru -1 of aList)
end if
return aList
end removeFromList