To address the conflict between trajectory fragmentation and the trade-off between association efficiency and data integrity in underwater micro-scale multi-target sonar motion detection and tracking in video sequences, a multi-target motion detection and tracking algorithm based on a dual trajectory storage mechanism and adaptive trajectory association is proposed. The method first obtains target centroids through Gaussian mixture model foreground extraction, morphological post-processing, and connected region analysis. By employing a dual-storage structure consisting of real-time trajectories and complete trajectories, it dynamically adjusts association thresholds based on frame sampling rates to achieve adaptive distance calculation for trajectory tracking. Experimental results demonstrate that the proposed method achieves a completeness rate of 100% in recording valid trajectory point lengths. The adaptive threshold mechanism improves association accuracy to 96.07% while reducing trajectory fragmentation rate to 0.9%. The average association time is 0.28 ms per frame, enabling efficient real-time association while ensuring the integrity of motion trajectory tracking. This research contributes to enhancing real-time detection and tracking capabilities for micro-scale underwater targets and provides support for applications such as underwater security surveillance, marine resource exploration, and intelligent autonomous underwater vehicle navigation.