Each set seems to have an official name. With the exception of the really early ones (1991-1992, with the "Super SONIC" tags), set names are on the white fabric tag. Dates are a bit trickier to pin down, without magazine/catalog images, but the fabric tag is a good guideline. The front of the fabric tag usually has a Sega copyright year (with the set name), which isn't much use, but the reverse (where it says "Made in ___") should have the actual production year.
Here's what I've managed to piece together so far, in terms of a release timeline and set names. For my own sanity I've stuck to the pre-Sonic Adventure stuff. Most of the set pics are small and poor quality, so if anyone has any better ones then please share. (All photos found online, can't remember where. A lot of them from Sonic Gear.)
ソニック・ザ・ヘッジホッグと仲間たちセット
Sonic the Hedgehog and Friends Set
1991, July

The original set. The set name is from a 1991 Sega arcade catalog. This ad seems to be saying that the launch date was July 15th? Seems a bit precise, so correct me if I'm wrong.

セガ・ソニック・ザ・ヘッジホッグと仲間たち3
Sega Sonic the Hedgehog and Friends 3
1992, August


So, obviously, there must have been a Sonic and Friends 2 at some point. I'll get to that in a later. This 1993 Sega prize / arcade catalog shows how many were in each assortment.
Eggman, Flicky, Pocky and Pecky are much the same, but the two Sonic dolls (sitting and standing) are of much higher quality, no longer having string limbs and felt feet.
Also notice that the branding has shifted from "Sonic" to "Sega Sonic". The paper tag has been adjusted too:
Pecky, in the middle, is a later (made in China) release with the SEGASONIC branding on the chunky black and white logo and the Japanese text on the bottom. Eggman and Flicky are the Set 1 (made in Korea) versions with the standard SONIC branding.
テイルス & エミー
Tails & Amy
1993

This one is a bit of guess work. There's a tiny set photo, but no official name associated with it. But the Tails and Amy dolls appear to be these ones, which say "Tails & Amy" (in Japanese) on the fabric tag:
So are there Sonic and Eggman dolls with "Tails & Amy" tags?
おめかしソニックと仲間たち
Dressing Up Sonic and Friends
1993

(This translation might be a little off.) Set name from the same 1993 catalogue as before, where it's advertised as "new". By this point the set names are on the fabric tag too. They all look to be based off the Tails & Amy set. Amy herself looks identical. Unsure whether there'd be two different Amys with two different fabric tags.
お祭りソニック&テイルス
Festival Sonic & Tails
1993, August

ソニック&テイルス サマーバージョン
Sonic & Tails Summer Version
1994

Set name and year from the fabric tag.
X'mas セガソニック
X'mas Sega Sonic
1994

Set name and year from the fabric tag. The reef itself is one of the prizes.
セガソニック スポーツ バージョン
Sega Sonic Sports Version
1995, February

ジャンボ セガソニック
Jumbo Sega Sonic
1995

You can't really tell in this tiny set photo, but these all have suction cups on their hands (or stomach, in Eggman's case). They're larger than most other sets, thus the name.
バスケット セガソニック
Basket Sega Sonic
1996, September

According to the Sonic Jam Official Guide these were released September 1996 (it calls them "Sega Sonic Basket", but both the paper and fabric tags say "Basket Sega Sonic"). This set is actually quite well made, as are the next two.
ソニック・ザ・ファイターズ
Sonic the Fighters
1997

The game was released in 1996, but the fabric tag says 1997. The May/June 1997 issue of Sega Magazine mentions them, not sure if it says anything interesting.
ソニック&テイルス ペールカラーぬいぐるみ
Sonic & Tails Pale Color Plush Doll
1998

The fabric tag says 1998.
Other Sets
Here's all the ones that I haven't been able to find set names or full details of:
Rubbery shoes Sonic
As seen here in Sega Magazine. Similar to the Sonic in the original set. The arms and legs are still stringy, but thicker. Instead of felt shoes he has rubbery/plasticy ones. Has the "Sega Sonic" branding. Possibly part of "Sega Sonic the Hedgehog and Friends 2"? Likely included Flicky/Pocky/Pecky/Eggman, like sets 1 and 3 did.
Go-Kart
Same as the "Sega Sonic and Friends 3" set, but they're in little plastic go-karts. No official set name known. Sonic Gear has photos of Eggman, Flicky and the two types of Sonic. Pecky also exists. Has anyone seen a Pocky?
Christmas Sonics
These predate the 1994 Christmas set. They're the same two Sonics from "Sega Sonic and Friends 3", but with festive bits and pieces added on.
Winking Sonic
I've only ever seen this one on Sonic Gear. It's the same as one of the "Sega Sonic and Friends 3" Sonics, but winking.
Goods Set
1994
セガソニックキーグッズセット ? Not sure about the part underlined. The Google Translate app failed me. Sega Sonic something Goods Set. "Key" goods set? That doesn't seem right. Anyway, no idea what else was in this set.
You can't really tell in this tiny set photo, but these all have suction cups on their hands (or stomach, in Eggman's case). Here's a photo I found of the fabric tag, if anyone can make out what it says (something Sega Sonic):
Mystery solved - thanks Zycor!
Soccer Sonic and Fan (??) Tails
These two have seemingly unique art on the paper tags. I'm not sure what Tails is carrying there. Anyway, if anyone owns either of these, it would be great if you could check the fabric tag for the set name.
Sonic, Tails and Rocky
A set with Sonic, Tails and a Rocky similar to the one from the Basket set, sans basket. I haven't been able to find any photos of the fabric tag, so I've no idea what this set is called. So if anyone has one and wouldn't mind taking a photo...